Методическое пособие Теория информации-2
.pdfзадаваемое минимальное кодовое расстояние должно быть не менее чем |
|
n% = 2x + 1. При этом длина кодового слова должна удовлетворять условию |
|
где = – |
N = = + P = 2 − 1, |
степень образующего многочлена, равная числу информационных |
|
символов; |
P – число контрольных символов; – любое целое число. |
Величина кодовой последовательности определяет число контрольных |
|
символов: |
P ≤ x = log> N + 1 ∙ x |
|
|
Данные коды могут быть не только двоичными, например коды Рида-
Соломона. Принципы построения и декодирования корректирующих БЧХ-
кодов основаны на полиномиальных операциях в полях Галуа (раздел теории
чисел, выдержки из которого для ознакомления приведены в Приложении 2).
Рассмотрим алгоритм построения двоичного БЧХ-кода. Для этого введём |
|||||
понятие примитивного многочлена. Многочлен |
|
Π|
степени P называется |
||
примитивным, если ˜ + 1 делится на Œ |
без остатка для ™ = 2Q − 1 и не |
||||
делится ни для какого меньшего значения |
™. Примерами примитивных |
||||
многочленов являются многочлены 1 + > |
+ c |
|
(делит j + 1, но не делит |
||
˜ + 1 для всех ™ < 7) и 1 + c + 8 (делит Š + 1, но не делит ˜ + 1 для всех |
|||||
™ < 15). |
|
|
|
|
|
Для построения кодирующего многочлена БЧХ-кода находят |
|||||
примитивный многочлен минимальной степени • |
– такой, |
что N ≤ 2¤ − 1 или |
|||
• ≥ log> N + 1 , где N – длина кодового слова. |
Пусть ¥ |
– корень данного |
|||
многочлена, тогда кодирующий многочлен представляет собой наименьшее общее кратное (НОК) примитивного и минимальных многочленов:
где = |
|
НОК |
}B |
(6.42) |
|
– |
многочлены минимальной степени, имеющие корни соответственно |
||||
¥, ¥ |
>, … , ¥ |
}B . |
|
x. Максимальный порядок |
|
|
Число |
минимальных многочленов |
равно |
||
|
|
|
191 |
|
|
минимальных многочленов можно определить по формуле = 2x − 1. Для построения кодирующего многочлена используют только нечётные многочлены.
Для случая двойных ошибок в качестве сомножителя выбирают минимальный многочлен для элементов поля ¥c; для тройных ошибок – минимальный многочлен для элементов поля ¥Š и т.д.
Построенный таким образом кодирующий многочлен производит код с минимальным расстоянием между кодовыми словами, не меньшим n, и длиной кодовых слов N.
Опознавателями ошибок для БЧХ-кодов считаются различные степени примитивного элемента поля ŒŽ 2¤ , построенного с использованием выбранного неприводимого многочлена Œ степени •, принадлежащего показателю степени N = 2¤ − 1. Так как число различных ненулевых элементов поля будет равно N, то каждому вектору ошибки в отдельном разряде можно
сопоставить свой опознаватель, что и гарантирует возможность исправления ошибок.
Суммы нечётных степеней опознавателей ошибок вычисляются по остаткам, получаемым в результате деления принятой кодовой комбинации на
соответствующий минимальный многочлен. |
|
|
N = 15 |
|
Пример. Построить БЧХ-код с длиной кодовых слов |
и |
|||
минимальным расстоянием между кодовыми словами |
n = 5, |
способный |
||
исправлять 2 кратные ошибки. |
|
• = log> N + 1 |
= |
|
Определим степень примитивного |
многочлена: |
|||
log> 16 = 4. Среди неприводимых многочленов 4-го порядка (см. Приложение |
||||
1) примитивным будет являться многочлен |
x8 + + 1. |
Его корнями будут |
||
¥, ¥>, ¥8. |
|
|
|
|
Порядок старшего из минимальных многочленов в таблице многочленов
(см. Приложение 1) будет = 2x − 1 = 3. Этот минимальный многочлен будет x8 + c + x> + + 1, следовательно:
192
НОК
=x8 + + 1 x8 + c + x> + + 1 =
=; + j + C + Š + 8 + Š + 8 + c + > + +
|
111110000 |
(6.42) |
+ x8 |
|
|
+ c + x> + + 1 = 000111110 |
= 111010001 = |
|
|
000011111 |
|
= ; + j + C + 8 + 1
Степень полученного многочлена равна 8, тогда построенный БЧХ-код будет обозначаться как (7, 15), где 7 – обозначает число информационных символов, а 15 – длина последовательности символов.
Первая строка образующей матрицы получается путём добавления слева от Œ такого числа нулей, чтобы общая длина кодовой комбинации была равна N. Образующая матрица (6.43) получается в результате = кратного циклического сдвига кодовой комбинации, соответствующей первой строке образующей матрицы.
000000111010001£
Ÿ000001110100010¢ Ÿ000011101000100¢
l 7,15 = Ÿ000111010001000¢ (6.43) Ÿ001110100010000¢ Ÿ011101000100000¢ ž111010001000000¡
Остальные комбинации кода получаются путём суммирования всевозможных сочетаний строк образующей матрицы. Таким образом, можно получить набор кодовых комбинаций из 128 элементов.
Кодирование информационной последовательности осуществляют следующим образом. Пусть дана информационная последовательность
1001101, которую требуется закодировать определенным выше БЧХ-кодом
(7,15). Образующий многочлен имеет восьмую степень, поэтому информационную комбинацию умножаем на одночлен той же степени, что и образующий многочлен, т.е. на 100000000. Получаем 100110100000000.
193
Полученную комбинацию делим по модулю 2 на образующий многочлен и получаем остаток равный 11000010 (рис. 6.12).
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
Рис. 6.12. Деление комбинации по модулю 2
Ещё раз подчеркнём, что деление по модулю 2 производится точно так же, как и привычное для нас деление «в столбик», но вместо вычитания в данном случае используется поразрядное сложение по модулю 2, т.е. каждый результирующий бит представляет собой функцию «Исключающее ИЛИ» от соответствующих битов слагаемых.
Полученный остаток от деления суммируют по модулю 2 с
информационной комбинацией, умноженной на одночлен той же степени, что и
образующий многочлен, т.е.
100110100000000 11000010 = 100110111000010,
где первые семь разрядов информационные, а остальные 8 – контрольные.
Обнаружение и исправление ошибок происходит по остаткам от деления принятой комбинации ‰ на образующий многочлен M . Если принятая комбинация делится на образующий многочлен без остатка, то код принят безошибочно. Остаток от деления свидетельствует об ошибке, но не указывает,
какой именно разряд принят ошибочно. Чтобы найти ошибочный разряд и исправить его в циклических кодах, принято осуществлять следующие процедуры:
1.Принятая комбинация делится на образующий многочлен.
2.Подсчитывается количество единиц в остатке (вес остатка). Если n ≤ x,
194
где -допустимое число исправляемых данным кодом ошибок, то принятая
комбинация складывается по модулю 2 с полученным остатком. Сумма даст
3.Если n > x, то производим. циклический сдвиг влево принятой
комбинации. Полученную в результате циклического сдвига комбинацию делят на образующий многочлен Œ . Если в остатке n ≤ x, то складываем делимое
состатком. Затем производим циклический сдвиг вправо полученной комбинации. Полученная комбинация уже не содержит ошибок.
4.Если после первого циклического сдвига и последующего деления остаток получается таким, что его вес n > x, то процедура (п.3) повторяется до тех пор, пока не будет достигнуто n ≤ x. В этом случае производиться
циклический сдвиг вправо на столько разрядов, на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получают исправленную комбинацию.
Рассмотрим процесс исправления ошибок в БЧХ-коде (7,15) на ряде примеров.
Пример. На приемном конце канала связи принята комбинация: 111001100000100. Делим принятую комбинацию на образующий многочлен
(рис. 6.13). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
||||||||||||||||||||||||
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Рис. 6.13. Деление комбинации 111001100000100 на образующий многочлен
Принятая комбинация делится на образующий многочлен без остатка,
следовательно, она передана без ошибок.
Пример. На приёмном конце канала связи принята комбинация: 111001100010100. Делим принятую комбинацию на образующий многочлен
195
(рис. 6.14). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
||
|
|
1 |
|
||||||||||||||||||||||||
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
|
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
Рис. 6.14. Деление комбинации 111001100010100 на образующий многочлен |
|||||||||||||||||||||||||||
n |
При |
делении |
получаем |
остаток |
10000, |
содержащий |
1, |
что |
говорит о |
||||||||||||||||||
|
|
искажённого |
бита |
в принятой последовательности. При этом |
|||||||||||||||||||||||
присутствии |
|||||||||||||||||||||||||||
= 1 ≤ x = 2, |
следовательно, |
требуется |
провести |
побитовое |
|
сложение |
|||||||||||||||||||||
принятой комбинации и полученного остатка, чтобы исправить ошибку (рис. 6.15). Исправленный бит выделен на рисунке полужирным начертанием.
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
Рис. 6.15. Побитовое сложение принятой комбинации и остатка от деления |
||||||||||||||||
Пример. На |
приёмном |
конце |
|
канала |
|
связи |
принята комбинация: |
|||||||||
111001000001100. Делим принятую комбинацию на образующий многочлен
(рис. 6.16).
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
Рис. 6.16. Деление комбинации 111001000001100 на образующий многочлен
В результате деления получаем остаток, содержащий 5 единиц,
196
следовательно n > x и требуется осуществить циклический сдвиг принятой
последовательности влево и провести деление новой последовательности на
образующий многочлен (рис. 6.17). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
||||||||||||||||||||||||
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
Рис. 6.17. Деление комбинации 110010000011001 на образующий многочлен
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
=4 > x = 2, выполняем циклический сдвиг
…ряд шагов не отображен (всего 12 сдвигов)…
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
, проводим суммирование данной комбинации с остатком |
|
||||||||||||||||||
Рис. 6.18. Последовательное деление комбинаций на образующий многочлен
197
Получаем остаток, содержащий количество единиц n > x, поэтому требуется еще раз осуществить циклический сдвиг и деление. Дальнейший ход проверки представлен на рис. 6.18. Поскольку в данном примере потребовался
12-кратный циклический сдвиг, то на рис. 6.18 представлен следующий и последний шаг.
Теоретически БЧХ-коды могут исправлять произвольное количество ошибок, однако с ростом кратности ошибки значительно возрастает длина кода,
что неизбежно ведёт к уменьшению скорости передачи и усложнению приемно-
передающей аппаратуры.
Итеративные коды Для итеративных кодов операции кодирования проводятся над
совокупностью информационных символов, располагаемых по нескольким,
например •, координатам. В связи с этим итеративные коды также называют многомерными, многостепенными. Число информационных символов в кодовом векторе -степенного кода вычисляется по формуле:
(6.44)
где =© – число информационных символов по координате γ.
Последовательности информационных символов по каждой из координат кодируются каким-либо линейным кодом. В общем случае каждый информационный символ входит одновременно в • различных кодовых векторов.
Классические итеративные коды. Идея создания рассматриваемых кодов принадлежит П. Элайесу. В этом случае определённым линейным кодом кодируется каждая из отдельных последовательностей информационных символов по координате γ (например, каждая строка). Получаемый итеративный код также является линейным.
Простейший из таких кодов является двухстепенной (двумерный) код с
198
проверкой на чётность по строкам и столбцам. Расположение информационных
и проверочных символов приведено на рис. 6.19.
|
|
|
|
|
Столбцы |
|
|
|
|
|
1 |
2 |
… |
|
… |
|
|
|
2 |
, |
,> |
… |
, |
… |
, B |
, |
|
1 |
>, |
>,> |
… |
>, |
… |
>, B |
>, |
Строки |
|
|
|
|||||
… |
…˜, |
˜,> |
… |
…˜, |
… |
˜, B |
…˜, |
|
|
|
|
… |
|
… |
|
||
|
|
|
|
… |
|
… |
|
|
|
… |
… |
… |
… |
… |
… |
… |
… |
|
|
)B , |
)B ,> |
… |
)B , |
… |
)B , B |
)B , |
|
|
|
|
… |
|
… |
|
|
|
|
), |
),> |
|
), |
|
), B |
), |
Рис. 6.19. Расположение информационных и проверочных символов в итеративном
двухмерном коде с проверкой на чётность по строкам и столбцам
Значения проверочных символов, располагающихся в крайнем правом
(или в любом другом) столбце и нижней строке, определяются уравнениями:
‰˜, = ‰˜, =«n 2 |
(6.45) |
|
|
‰), = ˜ ‰˜, =«n 2 |
(6.46) |
‰), = ˜ ‰˜, или ‰), = ‰), =«n 2 |
(6.47) |
Элемент ‰), проверяет на четность строку или столбец из проверочных символов.
Передачу символов такого кода обычно осуществляют последовательно
символ за символом, от одной строки к другой либо параллельно целыми строками. Декодирование начинают сразу, не ожидая поступления всего блока информации.
Проверка справедливости уравнений (6.45)-(6.47) при декодировании позволяет исправить любое нечётное число искажённых символов,
199
расположенных в одной строке или в одном столбце: строка (столбец) с
нечётным числом искажённых символов будет выявлена неудовлетворительным результатом проверки ее на чётность, а искаженные символы будут указаны при проверках по столбцам (строкам).
Необнаруженными оказываются только ошибки, имеющие чётное число искажённых символов как по строкам, так и по столбцам. Простейшая не обнаруживаемая ошибка содержит четыре искажённых символа,
расположенных в вершинах прямоугольника (рис. 6.20).
, |
,> |
… |
, |
… |
, B |
, |
… |
… |
|||||
>, |
0,0 |
|
0, |
|
>, B |
>, |
… |
… |
… |
… |
… |
… |
… |
˜, |
¯,0 |
… |
¯, |
… |
˜, B |
˜, |
|
|
|||||
… |
… |
… |
… |
… |
… |
… |
)B , |
)B ,> |
… |
)B , |
… |
)B , B |
)B , |
… |
… |
|||||
), |
),> |
|
), |
|
), B |
), |
Рис. 6.20. Пример необнаруживаемых ошибок в итеративном двухмерном коде с
проверкой на чётность по строкам и столбцам
Число ошибок такого вида y8′ для блока из # × N символов равно:
y8° = J>J)> = |
2! 2! |
(6.48) |
Общее число четырёхкратных ошибок составляет:
y8 = J8) = |
4! |
(6.49) |
Таким образом, отношение числа не обнаруживаемых четырёхкратных ошибок к общему числу таких ошибок составит:
y8 = N# − 1 N# − 2 N# − 3 (6.50)
8
Определим минимальный вес (количество единиц) ненулевого вектора рассматриваемого итеративного кода (двумерной кодовой комбинации). Такой
200