Параметрические оценки К-ичных и троичных ПСП-кодов в каналах со стиранием

УДК 50.41.25

А.А. Львов, М.С. Светлов, Ю.А. Ульянина

ПАРАМЕТРИЧЕСКИЕ ОЦЕНКИ К-ИЧНЫХ И ТРОИЧНЫХ ПСП-КОДОВ

В КАНАЛАХ СО СТИРАНИЕМ

Получены аналитические зависимости корреляционных свойств и избыточности для троичных и Личных кодов в системах передачи информации с каналами со стиранием.

Канал связи, ошибки стирания, автокорреляционные коэффициенты, избыточность, минимальное кодовое расстояние

A.A. L'vov, M.S. Svetlov, Y.A. Ul'yanina

PARAMETRIC ESTIMATES OF THE K-ARY AND TERNARY CAP-CODES IN CHANNELS WITH ERASURES

The analytical dependence of the correlation properties and redundancy for the ternary and the K-ary codes in data transmission systems with erasure channels.

Communication channel, erasing mistakes, autocorrelation coefficients, redundancy, minimum code distance

В классической теории кодирования для измерения расстояния между кодовыми словами принято использовать метрику Хемминга, в соответствии с которой расстояние между двумя любыми несовпадающими символами канального алфавита равно единице. Однако такое измерение кодового расстояния не позволяет полностью реализовать потенциал кода в виде псевдослучайных последовательностей (ПСП) по помехозащищенности, в частности определить точно зависимости между корректирующими свойствами (избыточностью) кодов и их корреляционными характеристиками. Целью данной статьи является получение аналогичных оценок с использованием метрики в соответствии с геометрической моделью кода на рис. 1.

d = 1

d = 1

d = 2

Рис. 1. Геометрическая модель кода Рис. 2. Математическая модель К-го канала с ошибками стирания

Математическая модель K-ичного канала с ошибками стирания (без ошибок трансформации) имеет вид:

K-1 ______

qo + £ Pox, =1 qi+Рх, =1 і=1K -1

¿=1

Здесь q0 и qi - вероятности правильного приема соответствующих символов; р0х и ріх -вероятности одиночных ошибок стирания.

В этом случае формулу для нижней границы избыточности по Хеммингу [1] можно представить в следующем виде:

e0 el eK-1 K "I

k й logk ZZ-I

i=1

где к - число контрольных разрядов кода; п - длина (число разрядов) кодовых слов; п0 -число нулевых символов кодового слова; щ - число ненулевых символов кодового слова; е - значение кратности исправления ошибок стирания; е0 - значение кратности исправления ошибок стирания для нулевых символов; е1 - значение кратности исправления ошибок стирания для единичных символов; ... еК _1 - значение кратности исправления ошибок стирания для символов (К - 1); dшin - значение минимального кодового расстояния.

Считая, что в формуле (1) равенство, ограничиваясь в ее правой части лишь старшими степенями параметра п и подставляя значение числа контрольных разрядов в формулу для определения коэффициентов избыточности [2], получим зависимость между коэффициентами избыточности кода и значением кратности исправления ошибок стирания для К-ичных

ПСП-кодов учитымя что е0 = 2*1 Рохе , по = 1 Рох,п, п = Рщп , ei = Рще , 1 = 1, К _1:

R = k

( k-1 Y (к -11 Z Po „ _ V i=1 )_ K-1 P e 1"P0П (P,i)' П [Px,e]! ( K-1 K-1 e\ Z PoXi + Z P V i=1 ' i=1

Kk K-1 Z Pox, e i=1 !

Принимая во внимание, что е = dшin _ 1, и считая, что значения ^т|п минимального кодового расстояния при вычислении коэффициентов корреляции совпадают со значениями кодового расстояния d в формуле вычисления нормированных коэффициентов автокорреляции [2], получим выражения для определения значений коэффициентов избыточности через минимальное кодовое расстояние:

R=k

(K

K-1

ZPoxi

X (dmin 11

.П-^___________

toPix (dmin-1)]L

Kk

Tp0,

i=1

( K-1 K-1

(dmin-1)| ZP0xi + ZPix

Учитывая, что d = п(1 _р)/2, получим формульную зависимость между нормированными автокорреляционными коэффициентами и значением коэффициентов избыточности:

R = k

( k-1 ) (к -11 Z Pox, _ V i=1 )_ KZP \ “(1-p) il Z1Poxi V 2 1J k-1 = 1 -n- i=1 kH 2 -1

P-( "Г-1)]

Kk [Щ -1)] !

n(1-p) Л(K-1 K-1

ZPoxi + Zpix

Поскольку на практике наиболее часто используемыми ПСП-кодами являются троичные коды, благодаря их свойствам по помехозащищенности, рассмотрим отдельно случай троичного канала. Преобразуем модель К-ичного канала к виду троичного, учитывая, что I = 1, 2.

to и

K-1

Для случая троичного канала. Формула для нижней границы избыточности (2) перепишется в виде:

«о « «2 2

к г III2'°С£П.

% ?1 ?2

,=1

Тогда зависимость между коэффициентами избыточности и кратностью исправления ошибок стирания определится по формуле (7):

Я = к

" I 2 V 2| I Рох _ V ,=1 ) II Ро 2 ( Г4« ,=1 П (Р х) П [ Рх,«]! I 2 2 «| I Рох, +1 Р V ,=1 ' ,=1

3к 2 I Рох,« ,=1 !

Зависимость между коэффициентами избыточности и минимальным кодовым расстоянием выразится как:

Я = к

V

0 х, =1

I Рох, (Лт , =1

-1)

Рх,

П (рх)__________

П[Рх,(Лшп -1)]!

3к

Рох,

, =1

(Лшш -1)| I Рох, + I Ра =1 г ,=1

Нормированные коэффициенты избыточности как функции нормированных коэффи-

циентов автокорреляции запишутся в виде:

г п

Я = к

г: Ро х, | -1 ] 2

П

рх1п(12р -1

, п(1 -р) ,

Рх1 —2-------------1

3к

I Р Iп

Ро

-1

,=1 ‘ V 2

Приведенные зависимости справедливы для несимметричных каналов, однако на практике при моделировании чаще рассматриваются симметричные каналы. Адаптируем полученные выше результаты на случай симметричного канала. Симметричным считаем канал, в котором выполняются равенства:

«о «1 «2 .•

. = еК-1 = ^ ; по = п1 = П2

... = ПК-1 = пх

С учетом этих равенств формула для нижней границы избыточности (2) примет вид:

к г 1ое КI (К - 1)^ (СП; )К

Зависимость между коэффициентами избыточности кода и значением кратности исправления ошибок стирания для К-ичных ПСП-кодов (3) перепишется в виде:

к

Я

(Кк [(К - 1)Рх«] (К-1)Рх« [(РХ«) !]2

Зависимость между коэффициентами избыточности и минимальным кодовым расстоянием (4) определится по формуле:

Я = к

;=1

=1

Нормированные коэффициенты избыточности как функции нормированных коэффи циентов автокорреляции (5) запишутся в виде:

к(к-1) рх

R

Kk

(K -1) px

n

-1

N 2(K-1)Px ( "1-^-1

2 Pxl^ -1

Для троичного симметричного канала. Формула для нижней границы избыточности (6) примет вид:

k > iog3 j 2'XC';_  (c';_ )2.

Зависимость между коэффициентами избыточности кода и значением кратности исправления ошибок стирания для К-ичных ПСП-кодов (7) запишется в виде:

К = 2крх/

Зависимость между коэффициентами избыточности и минимальным кодовым расстоянием (8) будет находиться по формуле:

2 кРх

R

Нормированные коэффициенты избыточности как функция нормированных коэффициентов автокорреляции (9) перепишутся в виде:

2кРх

R = -

3'

1__

л 4 Px | "^-1

_1_____

••

_

Очевидно, что вероятность правильного приема ненулевых символов существенно выше вероятности правильного приема нулевых символов, поэтому целесообразно использовать коды без нуля.

Для K-ичного канала без нуля. Формулу для нижней границы избыточности (2) можно представить в следующем виде:

e1 e2 eK-1 K-1 t

k > log K EE... E П Cn‘ .

f1 f2 XK-1 i=1

Зависимость между коэффициентами избыточности и кратностью исправления ошибок стирания (3) определится следующим образом:

R = к

Pixie

1 П (PiXi ) Kk П [P,e]!

K-1

j PiXie i=1 *

Зависимость между коэффициентами избыточности и минимальным кодовым рассто янием (4) перепишется в виде:

1

I \Pixj min — 1)

1 ^1 (Р_Щ )_______________

R = к

Kk П [Pix, (dniin -1)]!

K-1 t \

j Pixi (dnin -1) i=1

Нормированные коэффициенты избыточности как функции нормированных коэффициентов автокорреляции (5) определятся по формуле:

R = k

і к-і

~КГ П

K і=і І

n (і-р) 1

Px, I ---:-----і

[ Pix

n

Для троичного канала без нуля. Формулу для нижней границы избыточности (6) можно представить в следующем виде:

«1 «2 2

к г 1о§з ЦПс1-

Ц Ґ2 і=і

Зависимость между коэффициентами избыточности и кратностью исправления ошибок стирания (7) определится следующим образом:

R = k

1.1 Pix, e

Зависимость между коэффициентами избыточности и минимальным кодовым рассто янием (8) перепишется в виде:

. 4p ,

/ \p,xі \dm.n і/ ; J-^i= i

_L П (pj

3k ПP x (dmin - і)]!

R = k

Нормированные коэффициенты избыточности как функция нормированных коэффициентов автокорреляции (9) будут находиться по формуле:

R = k

3Г П (Pij

n (і-р) _ 2

і=і

Для Личного симметричного канала без нуля. Формулу для нижней границы избыточности (10) можно представить в следующем виде:

k г log к Z (с

Зависимость между коэффициентами избыточности и кратностью исправления ошибок стирания (11) определится следующим образом:

К = кРх/

Зависимость между коэффициентами избыточности и минимальным кодовым расстоянием (12) перепишется в виде:

кРх

R =

K (к-і)px(dmin-і)[(px (dшп - і))і]

1 Px

Нормированные коэффициенты избыточности как функция нормированных коэффи циентов автокорреляции (1з) определятся по формуле:

кРх

R

k

K

(K-і)Px

n (і-р) 2

-і

У

n (і-р) ,

PxI ----:-----і

e

t

x

Для троичного симметричного канала без нуля. Формулу (14) можно представить в следующем виде:

« \2

k > iog3 ±

t,

Зависимость между коэффициентами избыточности и кратностью исправления ошибок стирания (15) определится следующим образом:

К = кРх/зЩ2Рх«)[

Зависимость между коэффициентами избыточности и минимальным кодовым расстоянием (16) перепишется в виде:

К = , -------------кРх---------------------------------------—-.

32Рх ^ -1)[

Нормированные коэффициенты избыточности как функция нормированных коэффициентов автокорреляции (17) определятся по формуле:

К =------------------------кРх-------------------------------------1-.

к Г п

3

т I ;

2 Рх\ -

2

2

Таким образом, получены аналитические зависимости между нормированными автокорреляционными коэффициентами и параметрами, характеризующими помехозащищенность, для троичных и К-ичных кодов. Использование этих выражений существенно упрощает оценки помехозащищенности систем, работающих в режиме исправления ошибок стирания, при анализе и синтезе цифровых систем передачи информации, использующих сложные ПСП-коды.

ЛИТЕРАТУРА

1. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки : М.: Мир, 1976. 593 с.

2. Светлов М.С., Ульянина Ю.А. О взаимосвязи избыточности и статистических характеристик троичных и K-ичных ПСП-кодов // АТМ-2011: сб. труд. II Международ. науч. конф. Т.2. Секция 2 / под ред. А.А. Львова и М.С. Светлова. Саратов: ООО «Издательство «Научная книга», 2011. С.65-68.

Львов Алексей Арленович -

доктор технических наук, профессор, заведующий кафедрой «Техническая кибернетика и информатика» Саратовского государственного технического университета имени Г агарина Ю.А.

Светлов Михаил Семенович -

кандидат технических наук, доцент кафедры «Техническая кибернетика и информатика» Саратовского государственного технического университета имени Г агарина Ю.А.

Ульянина Юлия Александровна -

магистрант кафедры «Техническая кибернетика и информатика» Саратовского государственного технического университета имени Гагарина Ю.А.

Статья поступила в редакцию 10.02.12, принята к опубликованию 12.03.12

x