Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

дов к . Эта граница достигается в том случае, если в про­ цессе кодирования каждый информационный символ

Мажоритарный принцип введения избыточности явля­ ется частным классом корректирующих кодов и может быть формально задан с помощью порождающей или контрольной матриц. Минимальное расстояние в таком коде равно 3 (этот факт следует из того, что строки порождающей матрицы содержат три единицы). Если информационные S{ и контрольные d разряды нумеро­ вать слева направо, то из приведенной матрицы Н сле­ дует, что каждый информационный символ описывается тремя независимыми уравнениями, первое из которых является тождеством:

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

Пусть /=3 , тогда k<^r. Принцип построения матри­ цы, обеспечивающей достижение верхней границы для к

41

(&=/•), показан на примере (8, 3, 4)-кода

Минимальное 'расстояние в этом коде равно трем. Из данной матрицы следует, что информационные и кон­ трольные символы низкоплотностного (п, 3, /г/2)-кода связаны соотношением

в котором индексы берутся да модулю /г. Из последнего соотношения следуют три уравнения для вычисления лю­ бого информационного разряда s,-, первое из которых является тождеством:

В уравнениях (2-8) индексы берутся по модулю k. Например, если i—1>=0, то значение индекса равно k и т. д. Таким образом, для декодирования (п, 3, /г/2)- кода могут быть использованы трехвходовые мажори­ тарные элементы.

Если / = 4 , то А^Зг/2 . Верхняя граница для It будет достигнута в том случае, если

Последнее 'неравенство будет справедливо при г ^ 4 . Другими словами, если /"^4 и является четным, то ра­ венство &=Зг/2 может быть удовлетворено. Если же г является нечетным числом, то может быть удовлетворено равенство &= (Зг—1)/2.

42

Аналогично могут быть рассмотрены низколлотностиые (п, } , А)-коды при />4 . Так как рассмотренные коды имеют d=3, то они могут быть получены из кодов Хэмминга с помощью укорачивания. .

где т > 3 — любое целое положительное число, а Ь<т —

следующим образом. Первая вектор-строка go состоит из

трицу, в качестве столбцов которой выбраны все возмож­ ные т-разрядные двоичные числа (начиная с нуля). Эти т строк gu ..., gm называют базисными векторами, первогог.порядка.:. Вычисляя -скалярные произведения пар gigj (L¥=j) базисных векторов первого порядка, получаембазисные векторы второго порядка. Базисные векторы третьего порядка равны скалярному произведению трех векторов первого порядка и т. д. Таким образом, если

43

строится матрица G для кода порядка б, то она содер­ жит

В данном кодовом векторе нельзя указать какие из разрядов являются информационными, а какие — кон­ трольными.

Процесс декодирования (извлечения информационно­ го слова из кодового) кодов Р—М отличается от декоди­ рования кодов Хэмминга. Это отличие заключается в том, что каждый из информационных символов st- может быть описан не менее чем <i=2 m - s независимыми уравнениями (контрольными соотношениями), аргументами которых являются символы bi кодового слова. Анализ результа­ тов решения этих уравнений по принципу большинства позволяет определить значения s,-. Тем самым при исправлении ошибок исключается этап определения ме­ ста ошибок, как это имело место в случае ранее рас-

44

смотренных кодов. Поэтому говорят, что коды Р—М по­ зволяют использовать мажоритарный принцип декодиро­ вания.

Простота структуры порождающей матрицы G, соот­ ветствующей кодам Р—М, позволяет установить связь между Si и Ь;, т. е. записать контрольные соотношения без обращения к специальным алгебраическим приемам. В первую очередь записываются уравнения для симво­ лов Si, соответствующих базисным векторам наивысшего порядка i&, затем — порядка (6—1) и т. д. «Соответствие» между информационными символами s,- и базисными

цах матрицы G показывают, какие именно информацион­ ные символы Si определяют значения символов bj кодо­ вого слова.

Например, из приведенной матрицы следует, что

6i=50 -rS4;

Поэтому общий принцип поиска контрольных соотно­ шений заключается в том, чтобы найти такие совокуп­ ности столбцов матрицы G, сумма которых является век­ тором, только одна координата которого равна 1. Место­ положение этих столбцов указывает, какие символы bj входят в данное соотношение.

Например, в приведенной матрице сумма первых че­ тырех столбцов равна 00 ... 01. На основании этого мож­ но записать уравнение связи

45