Главная > Теория связи > Введение в теорию помехоустойчивого кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2. Коды с d=4

Линейные формы, представляющие проверочные символы кодов с , в принципе находятся так же, как и в случае кодов с . Для построения кода с необходимо и достаточно найти матрицу порядка , удовлетворяющую условиям: 1) каждая строка матрицы содержит не менее трех отличных от нуля элементов данного поля; 2) в результате нетривиальной суммы любых двух строк образуется -значная комбинация, содержащая не менее чем два отличных от нуля элемента данного поля; 3) любые ее три строки линейно независимы. Доказательство этих положений легко производится с привлечением теоремы VII.5 и ее следствий.

Из сказанного сразу следует, что в кодах с число .

Для бинарного случая контрольная матрица кода с строится так. Сначала выписываются все -значные комбинации, содержащие точно три единицы, затем это множестбо дополняется комбинациями, имеющими точно пять единиц, семь единиц и т. д. Такая матрица удовлетворяет всем указанным выше условиям. Действительно, каждая ее строка содержит не менее трех отличных от нуля символов (по построению) и отличается одна от другой не менее чем в двух позициях. Сумма по модулю два двух любых строк приводит к комбинации, содержащей четное число единиц (строки отличаются в двух, четырех и т. д. позициях). В силу первого и второго свойств матрицы сумма трех ее строк приводит к комбинации, содержащей нечетное число единиц, что и доказывает их линейную независимость. Отсюда следует, что в бинарном коде с и заданным числом информационных символов число контрольных символов k определяется как минимальное, удовлетворяющее неравенству

(VIII.2.1)

где i пробегает все нечетные значения от 3 до .

Бинарные коды с легко строятся также на основе кодов с и следующего положения.

Теорема VIII.1. Если известен бинарный код с нечетным :

(VIII.2.2)

то для того, чтобы построить код с , достаточно дописать к каждой комбинации (VIII.2.2) еще один проверочный символ, определяемый линейной формой

(VIII.2.3)

Комбинации кода (VIII.2.2) содержат, d и более единиц. Следовательно, для того, чтобы увеличить число d на единицу, достаточно выбрать так, чтобы на позиции комбинации располагалась единица, если эта комбинация ранее содержала d (нечетное число) единиц, и любой символ, если в ней число единиц было более d. Как легко заметить, (VIII.2.3) удовлетворяет этому условию.

Соотношение (VIII.2.3) указывает один из возможных практических путей преобразования кода с в код с . Кроме того, для синтеза таких кодов при минимальном k могут быть использованы многотактные схемы с обратной связью типа описанных в § 1. Метод отыскания способа подсоединения ячеек регистра памяти к сумматору по модулю два остается таким же, как и в случае кодов с . Однако здесь контрольная подматрица должна удовлетворять условиям:

(VIII.2.4)

В табл. VIII.2 приведены результаты решения задачи методом неопределенных коэффициентов. Причем оказалось, что для кодеров типа рис. VIII.2 не существует. Для этого случая можно найти кодер типа гирлянды [172—173] (рис. VIII.3).

Таблица VIII.2.

Пусть к сумматору по модулю два подсоединены первая, вторая и третья ячейки памяти (рис. VIII.3а) Тогда после четырех тактов работы схемы базисная матрица кода запишется так:

(VIII.2.5)

Контрольная подматрица не удовлетворяет условиям (VIII.2.4) (две последние ее строки содержат только по две единицы). Задача теперь заключается в том, чтобы внести такие изменения в схему рис. (VIII.3,а), чтобы в результате этого в последнем столбце (VIII.2.5) трансформировать нули третьей и четвертой строк в единицы. Эта задача легко решается с помощью схемы рис. (VIII.3б). Здесь в цепь обратной связи дополнительно включается еще один сумматор по модулю два, на который подается сумма задержанная на три такта работы схемы. Выписав контрольную подматрицу, читатель может убедиться, что она удовлетворяет условиям (VIII.2.4).

Задача синтеза кодов с при в принципе решается так же, как и для бинарного случая. Интересно отметить, что для построения таких кодов с основанием и заданным требуется точно такое же число проверочных символов, как и для бинарных кодов.

Рис. VIII.3. Кодер типа гирлянды для кода (8, 4, 4).

<< Предыдущий параграф Следующий параграф >>
Оглавление