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

желательным. В этом случае необходимо предусматри­ вать только обнаружение ошибки (принятое слово содер­ жит ошибки, если корректор не равен нулю). Доля Pi обнаруживаемых ошибок кратности i ( i ^ 3 ) определяет­ ся из соотношений

возникновении которых сумма соответствующих столб­ цов матрицы Н не равна нулю.

Резюмируя вышесказанное относительно кода Хэмминга, можно отметить следующее: этот код с г кон­

В табл. 2-1 приведены параметры неукороченных кодов этого класса, 'представляющих интерес с точки зрения их использования в ЦВМ.

Значение отношения kin является важной характери­

в табл. 2-1 приведены параметры кодов с минимальным расстоянием d=4. Эти коды получаются из вышерассмотренных кодов Хэмминга добавлением одного кон­ трольного соотношения, представляющего собой резуль­ тат суммирования по модулю 2 всех разрядов кодового слова. При этом контрольная матрица Н [на примере

37

рассматриваемого нами кода (15, l l ) j имеет вид:

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 1 1 1,0 о о 1 1 1 1 о 1 о о о

Hje.u"—[J 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 I 0 I 0 I 0 0 0 I 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

В этом случае операция кодирования может выпол­ няться б два этапа. На .первом этапе вычисляется кодо­ вое слово при использовании матрицы Н, соответствую­ щей коду с d=3, а на втором этапе добавляется один дополнительный .контрольный разряд, в котором записы­ вается результат суммирования по модулю 2 всех раз­ рядов кодового слова, полученного на первом этапе. Таким образом, коды Хэмминга с d=A имеют парамет­ ры: п—2г разрядов, из которых (г + 1) являются кон­ трольными.

из двух самостоятельных операций: 1) вычисления /--раз­ рядного корректора, соответствующего коду с d=3; 2) .проверки последнего контрольного соотношения. Воз­ можные результаты выполнения этих операций и соот­ ветствующие им выводы приведены в табл. 2-2.

Дополнительное контрольное соотношение, вводимое для увеличения минимального расстояния кода Хэммин­ га, можно представить следующим образом:

38

Учитывая (2-6), после линейных преобразований по­ лучаем:

Система уравнений (2-6) и шоследнее соотношение для с5 позволяет записать контрольную -матрицу для рас­ сматриваемого разделимого кода в виде

Если контрольная матрица кода с минимальным рас­ стоянием d=4 приведена к виду Н = ||А1||, то процедура декодирования может выполняться следующим образом:

1)вычисляется корректор;

2)сравнивается корректор (если последний не равен

нулю) с вектор-столбцами матрицы Н и при совпадении с одним из столбцов фиксируется местоположение ошиб­

Иногда при практическом использовании кодов встречается за­ дача получения укороченного кода с заданным минимальным рас­ стоянием (d=3 или 4). Пусть, например, требуется получить - код, содержащий 10 информационных разрядов (4=10). Из табл. 2-1 видно, что неукороченные коды содержат k=A разряда, что недоста­ точно, или k—М разрядов, что больше требуемого. Укороченный код строится следующим образом. Записывается матрица Н для неуко­ роченного кода (с требуемым минимальным расстоянием), в котором количество информационных разрядов k больше требуемого kr. За­ тем отбрасываются произвольные (k—k') столбцов подматрицы А и

38

Заметим, что формально процедуре отбрасывания определенных столбцов подматрицы А матрицы Н = ||А1|| соответствует приравнивание нулю соответствующих ин­ формационных разрядов. Отбрасывать можно любой столбец, «о предпочтительнее (с точки зрения экономии аппаратуры) тот из них, который содержит наибольшее количество единиц. Получаемые таким образом укоро­ ченные коды также являются групповыми.

Коды Хэмминга оптимальны в том смысле, что они требуют минимального количества дополнительных (кон­ трольных) разрядов.

:2 - 3 . НИЗКОПЛОТНОСТНЫЕ к о д ы

Трудности, связанные с практической реализацией де­ кодирования, заставляют искать специальные классы ко­ дов, для которых существует простой метод декодирова­ ния. К таким кодам относятся ннзкоплотностные коды.

Низкбплотностные коды описываются матрицей, со­ держащей преимущественно нули и сравнительно не­ большое число единиц. Тем самым уменьшается количе­ ство символов, входящих в контрольные' соотношения. Определим «изкоплотностный (п, j , k) -код как код дли­ ной п разрядов с к информационными разрядами и с контрольной матрицей, каждая строка которой содер­ жит не более / единиц.

Используя понятия контрольной матрицы Н, условия

трице Н не превышает г]. Если учесть, что контрольная матрица, соответствующая разделимому коду, имеет

любой из столбцов подматрицы А содержит по крайней мере две единицы (иначе не было бы удовлетворено условие 2), то k^.r(j—1)/2. Последнее неравенство яв­ ляется верхней границей для к .

40