Принципы построения циклических кодов.
Определенные комбинации циклического кода можно значительно упростить, если применить способ записи натурального двоичного кода с помощью единичной транспонированной матрицы.
22. Коды с обнаружением и исправлением ошибок. Циклический код: принципы построения циклического кода. Построить циклический (7, 4) код для образующего многочлена P(x)=х3+x2+1.
У этого кода n=7, k=4, m=3. Для построения используем единичную транспонированную матрицу.
Первая строка этой матрицы G(x)=1, поэтому G(x)*x3= x3. Далее выполняем деление на образующий многочлен и для этой строки получаем остаток 101 (табл. 4.20). Здесь же приведены результаты деления, выполняемого для других строк матрицы.
Вторая строка матрицы G(x)= x, поэтому G(x)*x3= x4. Деление на образующий многочлен даёт для этой строки остаток 111.
Аналогичные действия для третьей строки дают остаток 011, для четвёртой строки – остаток 110 .
Полученные остатки запишем в форме дополнительной матрицы контрольных элементов (табл. 4.21).
Вместо четырех операций деления можно провести одну, взяв в качестве делимого первую строку единичной матрицы Ik, умноженную на 1000 (х3) (табл. 4.22).
Таблица 4.20
Получение остатков для строк единичной транспонированной матрицы
Таблица 4.21
Дополнительная матрица контрольных элементов
Выписывая все частные остатки, получим дополнительную матрицу С3,4 для циклического кода (см. табл. 4.21).
Объединение единичной транспонированной матрицы с матрицей остатков даёт определяющую матрицу С*7,4 четырёхразрядного циклического кода (табл. 4.23).
Таблица 4.22
Получение частных остатков для единичной матрицы
Таблица 4.23
Определяющая матрица четырёхразрядного циклического кода
Из определяющей матрицы С*7,4 находят ненулевые комбинации путем сложения строк в различных сочетаниях.
23. Коды с обнаружением и исправлением ошибок. Циклический код: образующий многочлен, декодирование циклического кода.
Образующий многочлен.
Выбирается из числа неприводимых многочленов, некоторые из которых представлены в табл. 4.24.
Таблица 4.24
Неприводимые многочлены
Он должен иметь порядок (n-k)=m и входить в качестве сомножителя в состав двучлена (xn+1). Выбор P(x) влияет на корректирующие возможности циклического кода. Однократные и двукратные ошибки позволяют обнаружить следующие полиномы (табл. 4.25).
Таблица 4.25
Образующие многочлены для обнаружения единичных и двойных ошибок
|
n |
k |
m |
P(x) |
|
7 |
4 |
3 |
x3+x+1 |
|
15 |
11 |
4 |
x4+x+1 |
|
31 |
26 |
5 |
x5+x4+1 |
Декодирование циклических кодов.
Для обнаружения ошибок принятая комбинация циклического кода делится на образующий многочлен. Если результат не имеет остатка, то искажений нет, контрольные символы отбрасываются, и декодируется информационная часть.
Если имеется искажение, то искаженная комбинация:
H(x)=F(x)+E(x), где E(x) – многочлен ошибок, содержащий столько «1», сколько элементов искажено.
Для обнаружения и исправления ошибок существует несколько вариантов декодирования. Один из них заключается в следующем:
1. Вычисление остатка (как и при обнаружении ошибок).
2. Подсчет веса остатка w. Если w<=s (число исправляемых ошибок), то принятую комбинацию складывают по mod 2 с остатком и получают исправленную комбинацию.
3. Если w>s, то производят циклический сдвиг вправо (с переносом единицы из старшего разряда) на 1 разряд и полученную комбинацию делят на образующий многочлен. Если вес полученного остатка w1<=s, то циклически сдвинутую комбинацию суммируют по mod 2 с остатком R1 и затем циклически сдвигают ее в обратную сторону на 1 символ (на прежнее место), получают исправленную комбинацию.
4. Если одного сдвига вправо недостаточно, то сдвиг повторяют до тех пор, пока wi<=s, затем исправленную комбинацию возвращают на прежнее место.