стояние от переданной комбинации будет равно /. По этому при l^d—1 принятая кодовая комбинация не мо жет оказаться одной из разрешенных.
Для правильного декодирования с исправлением оши бок связь между кодовым расстоянием d и допустимым числом искаженных элементов t определяется следую щими соотношениями: если d нечетное число, то число
искаженных элементов не должно превышать •>'
если d четное число, то число искаженных элементов не
должно превышать |
. Сопоставляя эти соотноше- |
Y |
2 |
ния, видим, что оба выражения дают одинаковые значе ния допустимого числа искаженных элементов при d, равном 3 и 4, 5 и 6 и т. д.
Однако помехоустойчивость кода при четном значе нии d выше, чем при ближайшем меньшем нечетном. Так, нетрудно показать, что при четном d наряду с исправ
лением |
всех ошибок кратности, не превышающей |
(d—2)/2, |
одновременно обеспечивается обнаружение всех |
комбинаций, в которых искажены не более d\2 элемен тов. Например, при d—З избыточный код позволяет или исправлять одиночные ошибки в комбинациях, или обна руживать комбинации, число искаженных элементов ко торых не превышает двух. При d—4 избыточный код наряду с исправлением одиночных ошибок обнаружива ет комбинации, число искаженных элементов которых не
превышает двух. Соотношения 1^-—-и опре деляют лишь кратность гарантийно обнаруживаемых и исправляемых ошибок, наряду с которыми обычно обна руживается и исправляется часть ошибок и более высо кой кратности.
При использовании избыточных кодов для исправле ния и одновременного обнаружения ошибок более высо
кой кратности величина кодового расстояния |
при |
<l>t |
должна удовлетворять выражению d^l-\-t+\, |
|
где |
it— |
число обнаруживаемых ошибок; t — число |
исправляемых |
ошибок. |
|
|
|
|
Таким образом, задача построения избыточного кода |
сводится к выбору из N=2n |
кодовых комбинаций |
та |
ких N0 «-разрядных комбинаций, для которых обеспечи |
вается максимально возможное расстояние d. В |
общем |
виде эта задача до настоящего времени |
не решена. |
В |
табл. 6.3 приведены некоторые частные результаты, ус танавливающие связь между числом проверочных эле ментов г и числом элементов избыточного кода /г для различных d.
Т А Б Л И Ц А 6.3
Число проверочных элементов г
|
О |
|
1 |
|
> I o g 2 ( « + l) |
|
3slog2(2n) |
|
п( п— |
> l o g , [ 2 N + ( n — ! ) ( « — 2 ) |
|
n(n—1) |
>log2 |
— л ( п - l ) ( n - 2 ) |
6 |
|
П р и м е ч а н и е , |
л и"п могут п шшмать значе |
ние только целых |
чисел |
Существующие методы построения избыточных кодов решают в основном'задачу нахождения такого алгорит ма кодирования и декодирования, который позволял бы наиболее просто построить и реализовать код с задан ным значением d. Поэтому различные избыточные коды при одинаковых d сравниваются по сложности кодирую щего и декодирующего устройств. Этот критерий явля ется определяющим при выборе того или иного кода.
Коды, обладающие большей избыточностью, обла дают и большей помехоустойчивостью. Увеличение избы точности приводит к уменьшению производительности системы, так как значительно возрастает число элемен тов в кодовых комбинациях. Поэтому выбор кодов с оп ределенными корректирующими возможностями, а следо вательно, и с определенной избыточностью должен быть всегда строго обоснован, исходя из характера распреде ления ошибок в канале связи и получения необходимой достоверности принимаемой информации. Только при
таком подходе можно выбрать код с минимальной избы точностью и тем самым при обеспечении заданной до стоверности получить наибольшую производительность системы.
Реализация метода декодирования по критерию мак симального правдоподобия посредством сравнения при нятой комбинации с каждой из хранящихся в декоди рующем устройстве как разрешенной, так и неразрешен ной комбинацией практически возможна только при сра внительно малых п, т. е. когда число комбинаций N=2N невелико'1 ). Однако для получения высокой достоверно сти принимаемой информации с помощью избыточных кодов часто оказывается необходимым применять зна чения п порядка сотен. Поэтому основной задачей сов ременной теории кодирования является отыскание таких методов кодирования, которые позволяют осуществлять обнаружение 'и исправление ошибок не путем сравнения с хранящимися в памяти кодовыми комбинациями, а с помощью относительно простых операций, производимых
над принятой кодовой |
комбинацией. |
|
§ 6.3. ПРОСТЕЙШИЕ И З Б Ы Т О Ч Н Ы Е |
КОДЫ |
К о д с ч е т н ы м |
ч и с л о м е д и н и ц . |
Блочный код, |
образуемый добавлением одного элемента к комбина циям простого ^-элементного кода, представляет собой код с четньгм числом единиц при условии, что количе
ство единиц в кодовых комбинациях полученного |
ново |
го п = £4-1-элементного кода |
будет четным. Такой код |
характеризуется минимальным |
расстоянием d—2 |
и по |
этому согласно (6.9) позволяет обнаружить все кодовые комбинации, содержащие один искаженный элемент. На личие четного числа единиц в любой неискаженной ко довой комбинации дает возможность обнаружить все комбинации, в которых искажено нечетное число эле ментов. Избыточность кода с четным числом единиц Я —
=1/п минимальна.
Полагая, что искажения двух или более элементов в комбинации являются событиями взаимно независимыми, найдем вероятность обнаруживаемой и необнаруживае-
') Объем памяти декодирующего устройства должен быть рас считан на хранение п-2п дв. ед. Например, при л = 20 объем па мяти составляет порядка 2-107 дв. ед.
мой ошибок для данного кода. Вероятность обнаружи ваемой ошибки будет равна сумме вероятностей появле ния нечетного числа ошибок (одиночной, тройной и т . д . ) . Тогда согласно (6.7) получим
Р00 = С' pqn~l + С, 3 ,р 3 <Г 3 + Съпpq'1-5 + . . . (6.10)
Аналогично находим вероятность необнаруживаемых ошибок
L „ р q - f С„ р 4 о |
(6.11) |
Пренебрегая весьма малыми значениями вероятно стей ошибок, начиная с тройной, найдем отношение ве роятностей необнаруживае'мой и обнаруживаемой оши бок
В качестве примера, поясняющего образование кода с четным числом единиц, в табл. 6.4 приведен ряд комби наций шестиэлементного кода, первые пять элементов
|
Т Л Е Л |
II Ц А |
6.4 |
|
|
Т А Б Л И Ц А |
6.5 |
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
которого являются информационными, а шестой — про верочным. Избыточность этого кода R= 1/6« 0,166; от ношение числа необнаруживаемых к числу обнаруживае мых ошибок при р = Ю _ 3 составит 5 - Ю - 3 , т. е. на тыся чу обнаруживаемых ошибок приходятся пять необнару живаемых. Процедура декодирования такого кода сво дится к подсчету числа единиц в принимаемой комбина ции посредством двоичного элемента (триггера). Если но окончании приема комбинации двоичный элемент не вернулся в исходное положение, то это указывает на на личие искажений.
К о д с |
п о с т о я м |
н ы м в е с о м. К этому виду |
блоч |
ных кодов |
относятся |
все коды, в которых каждая |
раз- |
решенная комбинация содержит одинаковое число еди ниц. Число разрешенных комбинаций такого кода No оп ределяется как число сочетаний из п элементов по т, где т—вес кода:
Типичным примером кода с постоянным весом явля ется семиэлементный код, вес каждой разрешенной ком бинации которого равен трем. Из общего числа комби наций семиэлементного кода Л/ = 2 7 = 128, число разре шенных N0 составляет 35 (С^ ) . Некоторые комбинации такого кода приведены в табл. 6.5. Избыточность семи элементного кода с весом 3, подсчитанная по ф-ле (6.6), равна:
д = |
1 — ''°£2 3 |
5 |
^ 0 , 2 6 . |
|
log2 |
2' |
|
|
Минимальное кодовое расстояние |
кода с постоянным |
весом равно двум, т. е. такой |
код |
обнаруживает все |
одиночные ошибки. Однако, как видно из табл. 6.5, код с постоянным весом обнаруживает также двойные, тройные и т. д. ошибки одинаковых элементов, за исклю чением случаев, когда одна из единиц переходит в нуль, а один из нулей — в единицу. Искажение такого вида называется смещением. Очевидно, что при переходе двух единиц в нуль и двух нулей в единицу искажения также
|
|
|
|
|
|
|
|
|
не |
обнаруживаются. |
|
|
|
|
|
|
Определим |
помехоустойчивость |
n-элементиого |
ко |
да |
с весом т. Согласно (6.7) вероятность |
ошибочного |
приема одной из т единиц равна |
pqm~\ |
а |
вероят |
ность ошибочного |
приема одного из |
(п—т) |
|
нулей |
— |
С1п-т |
pqn~m~l- |
Если |
пренебречь весьма |
малой |
вероятно |
стью приема двух или более элементов, то вероятность необнаруживаемой ошибки
РВо = Cl pqm~l |
Сп-т pqn-m-1 |
= |
т(п- |
т) рг qn~2 = |
= т(п — т) р2(1 |
— р)п~~2 « |
т (л — т) р 2 [ 1 — (п — 2) р]. |
|
|
|
|
(6.13) |
Вероятность обнаруживаемой ошибки определим как |
разность |
|
|
|
|
^оо = Р« - Р»о « |
пр - т {п-m)p2 |
[1 - |
(п — 2) р\, (6.14) |
