где Рк |
— |
вероятность |
искажения |
комбинации, Я к = |
= 1 — i ( l — р ) п т а п р . |
|
|
|
|
|
|
Отсюда отношение вероятностей необнаруживаемой и |
обнаруживаемой ошибок будет |
равно: |
|
|
|
= |
Лю = |
пг (п — т) р2 |
[1 — (п — 2) р] |
_ |
|
|
Роо |
пр-т(п-т) |
р"-\\ — {п—2)р] |
|
|
= |
|
|
1 |
|
|
. |
(6.15) |
|
|
|
|
т |
|
_ , |
|
|
|
т(п—т) |
р2[1 — |
(п — 2) р] |
|
|
Для |
семиэлементного кода |
с |
весом |
3 |
выражение |
(6.15) примет вид |
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
Л = = |
|
7 |
|
|
|
|
|
|
|
|
12р(1-5р) |
1 |
|
|
|
|
|
|
|
|
5 |
|
|
Полагая |
р = 1 0 _ 3 |
, найдем, что т]= |
, т. е. пример- |
|
|
|
|
|
|
2940 |
|
|
но на три тысячи |
обнаруженных |
ошибок |
приходится |
пять необнаруженных. Это значит, что помехоустойчи вость семиэлементного кода с весом 3 при /? = 10~3 при мерно втрое выше помехоустойчивости шестиэлементного кода с четным числом единиц.
Ошибки при приеме комбинаций кода с весом т об наруживаются посредством счетчика единиц, коэффици ент счета которого равен т. Если по окончании приема комбинации счетчик не вернется в исходное положение,
это |
означает, |
что принятая комбинация |
|
искажена. |
|
К о д с ч и с л о м е д и н и ц , |
к р а т н ы м |
т р е м . |
Такой |
код |
строится |
аналогично коду |
с четным |
числом |
единиц: |
к кодовым комбинациям /^-элементного простого кода до
бавляются два проверочных элемента |
так, чтобы число |
единиц в кодовых комбинациях нового |
п = й + 2 - э л е м е н т - |
ного кода было кратно 3. Этот код позволяет обнаружить все одиночные и BGe четные ошибки одинаковых элемен тов (двойные, четверные и т. д . ) . Не обнаруживаются двойные ошибки вида смещения и тройные ошибки оди наковых элементов. Пренебрегая весьма малой вероят ностью появления тройных ошибок, можно считать, что необнаруженные ошибки будут иметь место только при наличии двойных ошибок типа смещения.
Согласно принципу |
построения кода |
любая |
п-эле- |
ментная комбинация |
может содержать |
3/ единиц, где |
i-—целое |
число, принимающее одно из значений |
1 , 2 , . . ., |
/. Причем |
/< — . Отсюда по аналогии с (6.13) |
напишем |
|
3 |
|
выражение, определяющее вероятность необнаруживаемой ошибки
о |
г \ „„3/—1 ^.1 |
3i — 1 |
(6.16) |
|
|
|
Нетрудно -показать, что Рт |
максимыльно пр.и мини |
мальном значении |
разности ^ |
3ij . |
|
Отношение вероятностей необнаруживаемой и обна руживаемой ошибок равно:
' к 'НО
В качестве примера, поясняющего построение кода с числом единиц, кратным трем, в табл. 6.6 приведены не-
|
|
|
|
|
|
Т А Б Л П Ц А |
|
6.6 |
|
|
|
|
|
Комбинации пятиэлементного |
Комбинации кода с числом единиц, |
кратным Э |
|
|
|
кода |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
3 |
4 |
5 |
1 |
|
2 |
3 |
|
4 |
5 |
6 |
7 |
1 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
|
|
1 |
1 |
1 |
1 |
1 |
которые комбинации семиэлементного кода, полученные добавлением к комбинациям обыкновенного пятиэлементного кода двух проверочных элементов. Наибольшее зна чение вероятность необнаруживаемой ошибки такого кода будет для комбинаций, содержащих три единицы:
Р н 0 = С3 pq2 C\pqs « 12 p V - |
(б-1 8) |
В случае, когда число единиц равно шести, Ря0 будет меньше.
Пользуясь (6.17), найдем отношение вероятностей не обнаруживаемой и обнаруживаемой ошибок
г, |
1 2 Р 2 ( 1 - Р ) 5 |
1 |
(6Л9) |
7 р - I 2 p 2 |
(1 — р)6 |
|
|
|
12рП—5р)
Сопоставляя (6.19) с аналогичным выражением для
кода с |
весом 3, видим, что 'при /г = 5 они 'равны, |
т. е. |
помехоустойчивость |
обоих кодов для искажений |
типа |
смещения |
одинакова. |
|
|
Рассматриваемый |
код обладает еще одной возмож |
ностью обнаружения ошибок: если первый проверочный элемент равен нулю, то второй всегда равен нулю. Эту особенность кода можно использовать при построении устройств, анализирующих правильность принимаемых комбинаций. Обнаружение ошибок в таком коде осуще ствляется посредством счетчика на 3.
К о р р е л я ц и е й и ы й к о д. Повышение эффективно сти кодов с обнаружением ошибок может быть достиг нуто не только увеличением их избыточности, но и вве дением определенных зависимостей между элементами кодовых комбинаций. Этог принцип использован в кор реляционном коде, для построения которого каждый эле мент обыкновенного (первичного) кода преобразуется в два элемента, при этом единица преобразуется в 10, а
нуль — в 01 |
(рис. 6.2). Таким образом, |
|
корреляционный |
код |
будет содержать |
вдвое |
боль- |
, . |
|
|
|
|
. |
|
|
|
. |
ше |
J |
|
г |
чем |
|
|
„ комбинации пеактого коаь |
элементов, |
|
первичный |
; |
0 |
|
i |
|
n |
n |
код. Поэтому |
независимо от чис- |
\ |
|
у |
|
\ |
|
|
|
|
|
лакоэффициенэлементов избыточностпервичноги кодакор- j\i \ |
|
|
|
|
|
|
|
|
|
реляционного |
кода R=\/2. |
|
[ \ |
|
|
\ |
I |
\ |
|
I |
\ |
Помехоустойчивость |
корреля- |
\ \ , |
|
|
I |
0 |
V |
0 |
I |
V |
ционных кодов обусловлена тем, 1 f 0 |
|
|
|
|
1 с< J |
что |
появление |
необнаруживае- |
KMSamV№ |
|
|
|
мрршционногоШо |
МОЙ 'Ошибки |
ВОЗ'МОЖИО |
только в Рис. |
|
6.2. Принцип |
фор |
том |
случае, |
когда |
два |
рядом |
рас- |
мир°вания |
элементов |
|
J |
|
|
г |
|
г |
корреляционного |
|
кода |
положенных |
элемента, |
|
соответст- |
|
|
|
|
|
|
|
|
|
|
вующих одному элементу первичного кода, будут иска жены так, что единица перейдет в нуль, а нуль — в еди
ницу. Вероятность |
такого события Рно |
= р2- Отсюда, зная |
Рно, найдем |
отношение вероятностей |
необнаруживаемой |
и обнаруживаемой |
ошибок |
|
|
|
_ |
р 2 |
р |
|
|
^ ~ |
Юр — р 2 |
~~ 10 — р |
Полагая |
р=>\0~3, |
получим |
т. е. примерно на де |
сять тысяч обнаруженных ошибок приходится одна не обнаруженная,
При симметричном канале эффективность корреляци онного кода с инверсией символов и с повторением сим волов будет одинакова. В случае же передачи по несим метричному каналу, для которого р1Фр°, эффективность корреляционного кода с инверсией символов будет выше.
Во всех рассмотренных выше случаях предполага лось, что при переходе от кода с числом элементов к к коду с числом элементов п вероятность искажений эле ментов оставалась неизменной. Это справедливо только в том случае, когда при переходе от одного кода к дру гому длительность передачи элементов то остается посто янной. При этом производительность системы уменьша ется во столько раз, во сколько п больше к.
И н в е р с н ы й к о д . В основу построения этого ко да, характеризующегося высокой эффективностью при простоте реализации, положен метод повторения исход ной кодовой комбинации. Причем передаваемая комби нация в зависимости от четного или нечетного числа еди ниц в ней либо просто повторяется, либо повторяется в инвертированном виде. Поясним сказанное на примере пятиэлементного кода.
Пусть пятиэлементная комбинация (табл. 6.7) содер жит четное число единиц. Тогда согласно принципу по
строения |
кода дополнительные пять элементов будут со- |
|
|
|
|
|
|
Т А Б Л И Ц А |
6.7 |
|
|
|
|
|
|
|
Комбинации |
|
первичного |
кода |
|
|
Комбинации |
инверсного |
кода |
|
|
|
основные |
элементы |
дополнительные элементы |
|
|
|
|
|
|
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 0 |
1 |
0 |
|
0 |
1 |
0 |
1 0 |
|
1 1 0 |
1 0 |
|
1 1 0 Т О ] |
|
1 |
0 0 |
|
1 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
впадать с основным. Если же передаваемая |
комбинация |
содержит |
нечетное число единиц, то дополнительные |
эле |
менты будут соответствовать инвертированной исходной комбинации. Таким образом, избыточность инверсного кода /?=0,5; а минимальное кодовое расстояние d—4 при любом к. Следовательно, такой код позволяет обна руживать все тройные ошибки. Однако благодаря внут ренней связи между элементами кодовой комбинации, что позволяет также рассматривать этот код как корре ляционный, необнаруженная ошибка будет иметь место 318
только в том случае, если одновременно исказятся два элемента в исходной комбинации и соответствующие им два элемента повторяемой комбинации. Вероятность по явления такого искажения приближенно может быть оп ределена из выражения
Ра0~С2п/2р\ |
(6.20) |
при п=ч10 получим Л ю ~ Ю 4 . Зная Рпо, |
найдем отноше |
ние вероятностей |
необнаруживаемой |
и обнаруживаемой |
ошибок |
|
|
|
|
|
ti - |
- |
= |
|
|
Л ; р3. |
|
Юр—Юр* |
|
1 |
|
|
Полагая р = 1 0 ~ 3 , получим |
п = |
— |
, т. е. на 109 обна- |
г |
|
|
1 |
10э |
|
руживаемых ошибок будет приходиться одна необнаруживаемая.
Процедура обнаружения ошибок при приеме комби наций инверсного кода состоит из двух операций. Сна чала суммируются единицы, содержащиеся в первых я/2 элементах. Если их окажется четное число, то вторые /г/2 элементов принимаются в прямом виде. После этого обе зарегистрированные комбинации сравниваются по
элементно (первый элемент |
с первым, второй |
со вторым |
и т. д.) : ) |
и при обнаружении хотя бы одного |
несовпаде |
ния вся |
последовательность |
из п элементов |
бракуется. |
Если же количество единиц среди первых /г/2 элементов нечетное, то вторые /г/2 элементов принимаются инвер тированными. Затем, как и в предыдущем случае, обе зарегистрированные комбинации сравниваются поэле ментно. Наличие несовпадений указывает на то, что при нятая комбинация искажена (табл. 6.8, элементы, при нятые с искажением, обведены).
Инверсный код (d=A) можно использовать и для ис правления одиночных ошибок. Предположим, что в при нятой комбинации-один из элементов искажен (столбец а). Если этот элемент расположен в первой половине ко довой комбинации, то при сложении по модулю два пер вой и второй половин кодовых комбинаций совпадает только одна пара, что является признаком искажения
') Операция поэлементного сравнения кодовых комбинаций представляет собой поразрядное сложение их по модулю два.
