Теория информации (стр. 24 из 29)
Схема кодирующего устройства приведена на рис. 4.6.
Рис. 4.6.
При поступлении импульса синхронизации со схемы управления подлежащая кодированию k-разрядная комбинация неизбыточного кода переписывается, например, с аналого-кодового преобразователя в информационные разряды n-разрядного регистра. Предположим, что в результате этой операции триггеры регистра установились в состояния, указанные в табл. 4.9.
С некоторой задержкой формируются выходные импульсы сумматоров С1, С2 С3, которые устанавливают триггеры проверочных разрядов в положение 0 или 1 в соответствии с приведенными выше равенствами. Например, в нашем случае ко входам сумматора C1 подводится информация, записанная в 3, 5 и 7-разрядах и, следовательно, триггер Тг1 первого проверочного разряда устанавливается в положение 1, аналогично триггер Тг2 устанавливается в положение 0, а триггер Тг4 — в положение 1.
Сформированная в регистре разрешенная комбинация (табл. 4.10) импульсом, поступающим с блока управления, последовательно или параллельно считывается в линию связи. Далее начинается кодирование следующей комбинации.
Рассмотрим теперь схему декодирования и коррекции ошибок (рис. 4.7), строящуюся на основе совокупности проверочных равенств. Длякода (7, 4) ониимеютвид:
a1
a3 a5 a7= 0 ,a2
a3 a6 a7= 0,a4
a5 a6 a7= 0 .Таблица 4.9.
| Тr1 | Тr2 | Tr3 | Тr4 | Тr5 | Tr6 | Тr7 |
| — | — | 1 | — | 0 | 1 | 0 |
Кодовая комбинация, возможно содержащая ошибку, поступает на n-разрядный приемный регистр (на рис. 4.7 триггеры Тг1 –Тг7). По окончании переходного процесса в триггерах с блока управления на каждый из сумматоров (C1 – С3) поступает импульс опроса.
Таблица 4.10.
| Тг1 | Тг2 | Тг3 | Тг4 | Тг5 | Tг6 | Тг7 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 |
Рис. 4.7.
Выходные импульсы сумматоров устанавливают в положение 0 или 1 триггеры регистра опознавателей. Если проверочные равенства выполняются, все триггеры регистра опознавателей устанавливаются в положение 0, что соответствует отсутствию ошибок. При наличии ошибки в регистр опознавателей запишется опознаватель этого вектора ошибки. Дешифратор ошибки DC ставит в соответствие множеству опознавателей множество векторов ошибок. При опросе выходных вентилей дешифратора сигналы коррекции поступают только на те разряды, в которых вектор ошибки, соответствующий записанному на входе опознавателю, имеет единицы. Сигналы коррекции воздействуют на счетные входы триггеров. Последние изменяют свое состояние, и, таким образом, ошибка исправлена. На триггеры проверочных разрядов импульсы коррекции можно не посылать, если после коррекции информация списывается только с информационных разрядов. Для кода Хэмминга (7,4) любой опознаватель представляет собой двоичное трехразрядное число, равное номеру разряда приемного регистра, в котором записан ошибочный символ.
Предположим, что сформированная ранее в кодирующем устройстве комбинация при передаче исказилась и на приемном регистре была зафиксирована в виде, записанном в табл. 4.11.
Таблица 4.11.
| Тг1 | Тг2 | Тг3 | Тг4 | Тг5 | Тг6 | Tг7 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
По результатам опроса сумматоров получаем:
на выходе С1a1
a3 a5 a7= 1+1+1+0=1,на выходе С2a2
a3 a6 a7= 0+1+1+0=0,на выходе С3a4
a5 a6 a7= 1+1+1+0=1 . 
Рис. 4.8.
Следовательно, номер разряда, в котором произошло искажение, 101 или 5. Импульс коррекции поступит на счетный вход триггера Тг5, и ошибка будет исправлена.
Пример 34. Реализуем мажоритарное декодирование для группового кода (8,2), рассчитанного на исправление двойных ошибок.
В случае мажоритарного декодирования сигналы с триггеров приемного регистра поступают непосредственно или после сложения по модулю два в соответствии с уравнениями системы разделённых проверок на мажоритарные элементы М, формирующие скорректированные информационные символы.
Схема декодирования представлена на рис. 4.8. На входах мажоритарных элементов указаны сигналы, соответствующие случаю поступления из канала связи кодовой информации, искаженной в обоих информационных разрядах (5-м и 8-м). Реализуя принцип решения «по большинству», мажоритарные элементы восстанавливают на выходе правильные значения информационных символов.
4.9 Построение циклических кодов
4.9.1 Общие понятия и определения
Любой групповой код (n, k) может быть записан в виде матрицы, включающей kлинейно независимых строк по nсимволов и, наоборот, любая совокупность kлинейно независимых n-разрядных кодовых комбинаций может рассматриваться как образующая матрица некоторого группового кода. Среди всего многообразия таких кодов можно выделить коды, у которых строки образующих матриц связаны дополнительным условием цикличности.
Все строки образующей матрицы такого кода могут быть получены циклическим сдвигом одной комбинации, называемой образующей для данного кода. Коды, удовлетворяющие этому условию, получили название циклических кодов.
Сдвиг осуществляется справа налево, причем крайний левый символ каждый раз переносится в конец комбинации. Запишем, например, совокупность кодовых комбинаций, получающихся циклическим сдвигом комбинации 001011:
Число возможных циклических (n,k)-кодов значительно меньше числа различных групповых (n,k)-кодов.
При описании циклических кодов n-разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной х. Показатели степени у xсоответствуют номерам разрядов (начиная с нулевого), а коэффициентами при х в общем случае являются элементы поля GF(q). При этом наименьшему разряду числа соответствует фиктивная переменная х0 = 1. Многочлен с коэффициентами из поля GF(q) называют многочленом над полем GF(q). Так как мы ограничиваемся рассмотрением только двоичных кодов, то коэффициентами при х будут только цифры 0 и 1. Иначе говоря, будем оперировать с многочленами над полем GF(2). Запишем, например, в виде многочлена образующую кодовую комбинацию 01011:
G(x) = 0·x4 + 1·x3 + 0·x2 + 1·x + 1
Поскольку члены с нулевыми коэффициентами при записи многочлена опускаются, образующий многочлен:
G(x) = x3 + x + 1
Наибольшую степень х в слагаемом с ненулевым коэффициентом называют степенью многочлена. Теперь действия над кодовыми комбинациями сводятся к действиям над многочленами. Суммирование многочленов осуществляется с приведением коэффициентов по модулю два.
Указанный циклический сдвиг некоторого образующего многочлена степени n - kбез переноса единицы в конец кодовой комбинации соответствует простому умножению на х. Умножив, например, первую строку матрицы (001011), соответствующую многочлену g0(х) = x3 + x + 1, на х, получим вторую строку матрицы (010110), соответствующую многочлену х • g0(x).
Нетрудно убедиться, что кодовая комбинация, получающаяся при сложении этих двух комбинаций, также будет соответствовать результату умножения многочлена x3 + x + 1 на многочлен x+1. Действительно,
Циклический сдвиг строки матрицы с единицей в старшем (n-м) разряде (слева) равносилен умножению соответствующего строке многочлена на х содновременным вычитанием из результата многочлена хn + 1= хn– 1, т. е. с приведением по модулю хn + 1.