1601

формируют проверочные разряды и сравнивают их с принятыми; если они не совпадают, значит, при передаче произошла ошибка. Существуют коды, обнаруживающие факт искажения сообщения, и коды, исправляющие ошибки, т.е. такие, с помощью которых можно восстановить первичную информацию.

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

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно.

Количество контрольных разрядов r должно быть выбрано так, чтобы удовлетворялось неравенство 2r≥k+r+1 или r≥log2(k+r+1), где k

– количество основных двоичных разрядов кодового слова. Минимальные значения r при заданных значениях k, найденные

в соответствии с этим неравенством, приведены в табл. 2.3.1.

Таблица 2.3.1

Минимальные значения r при заданных значениях k

Так, классический код Хемминга (7,4,3) содержит всего 7 разрядов, из которых 4 информационных, а 3 контрольных.

Величину r называют избыточностью корректирующего кода. n

Введение избыточности в кодовые комбинации при использовании корректирующих кодов существенно снижает скорость передачи информации и эффективность использования канала связи.

Особый интерес представляют двоичные групповые (блочные) корректирующие коды. Групповым называется код, который образует алгебраическую группу по отношению к операции сложения по моду-

30

лю два. При использовании таких кодов информация передаётся в виде блоков одинаковой длины, и каждый блок кодируется и декодируется независимо от других. В блочных кодах символы можно разделить на информационные и проверочные. Таким образом, все комбинации кодов разделяются на разрешенные и запрещенные.

Различают несистематические и систематические коды.

В несистематических кодах проверочные разряды занимают те позиции кодового слова, которые содержат только одну единицу (в двоичном представлении номера позиции разряда: 1,10,100,1000…). Эти позиции соответствуют номерам, кратным степени двойки (20=1, 21=2, 22=4, 23=8,…): 12=1, 22=10, 42=100, 82=1000,…

В несистематическом коде вид синдрома (указателя разряда, где есть ошибка) представляется двоичным числом, которое представляет собой номер ошибочного разряда.

Пусть требуется передать некоторое слово 1001, содержащее 4 информационных разряда (k=4), с помощью несистематического кода, исправляющего одну одиночную ошибку.

Nk=2k=24=16. Из условий 2r≥n+1 и n=k+r имеем 2r≥k+r+1=4+r+1=5+r, откуда r=3. Кодовое расстояние определится из условия d≥2p+1, где p – число исправляемых ошибок. При p=1 dmin=3.

Таким образом, для передачи этого слова потребуется 7 разрядов: 4 информационных и 3 контрольных.

Условное обозначение кодового 7-разрядного слова в несистематическом коде Хемминга (7,4) приведено в табл. 2.3.2.

Таблица 2.3.2

Кодовое 7-разрядное слово в несистематическом коде Хемминга (7,4)

Контрольные разряды с0, с1, с2 помечены темным фоном. Информационные разряды а0, а1, а2, а3 известны. Для определения проверочных разрядов выполним следующие действия.

Заполним табл. 2.3.3 от с0 до а3 двоичными трехразрядными (r=3) числами от 001 до 111, располагая разряды в соответствии с табл. 2.3.2. Младшие разряды чисел обозначены цифрой 1, старшие – цифрой 3.

31

Таблица 2.3.3

Двоичные трехразрядные числа

Просуммируем по модулю 2 единичные значения каждой из трех строк и приравняем сумму к нулю.

с2 а1 а2 а3=0; с1 а0 а2 а3=0; с0 а0 а1 а3=0.

Решив полученную систему уравнений, находим значения с0, с1, с2 и заносим их в табл. 2.3.4.

Таблица 2.3.4

Кодовое слово с контрольными разрядами

Двоичное число с2 а1 а2 а3 с1 а0 а2 а3 с0 а0 а1 а3 является указателем разряда, где есть ошибка, и называется синдромом ошибки S. Если S=000, кодовая комбинация передана без искажений.

Предположим, что кодовое слово было передано без искажений, тогда проверка контрольных соотношений приведет к результату

с2 а1 а2 а3=0;

с1 а0 а2 а3=0; (2.3.1)

с0 а0 а1 а3=0.

Так как в данном случае информация передана без искажений, S=000. Информационное слово I получается из кодового слова С путем отбрасывания контрольных разрядов:

32

Предположим теперь, что на приемной стороне было получено кодовое слово С*, в котором в разряде а2 вместо 0 оказалась 1.

С*=1101100. (2.3.3)

Это означает, что кодовое слово было принято с ошибкой, тогда проверочные равенства в приемнике дадут синдром ошибки:

с2 а1 а2 а3=1 0 1 1=1; с1 а0 а2 а3=0 1 1 1=1; (2.3.4) с0 а0 а1 а3=0 1 0 1=0.

Полученный синдром S=110 указывает, что ошибка произошла в шестом разряде (1102=6) и, значит, шестой разряд надо исправить (просто инвертировать). Тогда будем иметь

Далее информационное слово I получается из кодового слова С путем отбрасывания контрольных разрядов:

Так можно обнаружить и исправить любую однократную ошибку (в любом разряде).

В систематическом коде информационное слово занимает первые k разрядов, проверочное – оставшиеся n–k.

Для кода (7,4) кодовое слово имеет вид, приведенный в табл.

2.3.5.

Таблица 2.3.5

Кодовое 7-разрядное слово в систематическом коде Хемминга (7,4)

Информационные разряды аi являются элементами единичной матрицы k×k. В систематическом коде номер ошибочного разряда оп-

33

ределяется по синдрому с помощью матрицы H(n, k). Номер столбца, совпадающий с синдромом, соответствует разряду кодового слова, который содержит ошибку.

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами k и n. Число строк равно k, а число столбцов равно n=k+r.

... ... ... ... ... ... ... ...

ak1 ak2 ...akk pk1 pk2 ... pkr

Коды, порождаемые этими матрицами, называются (n,k)-кодами, а соответствующие им матрицы – порождающими (образующими, производящими). Порождающая матрица G состоит из информационной Ikk и проверочной Rkr матриц. Порождающая матрица является сжатым описанием линейного кода и может быть представлена в канонической (типовой) форме

В качестве информационной матрицы удобно использовать единичную матрицу, ранг которой определяется количеством информационных разрядов:

Строки единичной матрицы представляют собой линейно независимые комбинации, т.к. их попарное суммирование по модулю два не приводит к нулевой строке.

Пусть требуется передать кодовое слово 1101, содержащее 4 информационных разряда (k=4), но с помощью систематического кода, исправляющего одну одиночную ошибку.

34

Как было установлено, Nk=2k=24=16. Из условий 2r≥n+1 и n=k+r имеем 2r≥k+r+1=4+r+1=5+r, откуда r=3. Кодовое расстояние определится из условия d≥2p+1, где p – число исправляемых ошибок. При p=1 dmin=3.

Для кода (7,4)

Строки порождающей матрицы представляют собой первые k комбинаций корректирующего кода (информационная матрица Ikk). Последующие r столбцов порождающей матрицы представляют собой корректирующие разряды с0, с1, с2, предназначенные для обнаружения или исправления ошибки в информационной части кода. Это проверочная матрица Rkr. Вес каждой строки проверочной матрицы (количество единиц в строке) должен быть

где WIkk – вес каждой строки информационной матрицы.

В качестве строк проверочной матрицы R43 могут быть выбраны трехзначные двоичные комбинации с числом единиц, большим или равным двум: 111; 110; 101; 011.

Окончательный вид проверочной матрицы:

(2.3.12)

Как видно, основным требованиям могут удовлетворять несколько матриц. Выбор матрицы определяется по дополнительным требованиям: минимум корректирующих разрядов или максимальная простота аппаратуры. Полученную комбинацию в виде проверочной матрицыRkr приписывают справа к информационной матрице и получают порождающую матрицу корректирующего кода.

Выберем четвертую из приведенных матриц. Тогда порождающая матрица кода G(7,4) примет вид

n

Столбцы проверочной матрицы Rkr определяют правила формирования проверок.

Процесс кодирования состоит во взаимно-однозначном соответствии k-разрядных информационных слов I и n-разрядных кодовых слов С.

Произведение информационного слова на порождающую матрицу дает кодовое слово C=IG.

Информационному слову I=1101 соответствует следующее кодовое слово:

Процесс декодирования состоит в определении соответствия принятого кодового слова переданному информационному. Это осуществляется с помощью матрицы H(n, k).

где RkrT – транспонированная проверочная матрица (поменять строки на столбцы); Irr – единичная матрица.

Проверочная матрица строится следующим образом. Вначале

К полученной матрице справа приписывается единичная квадратная матрица Irr.

Таким образом, H(7,4) R43T I33.

В данном примере

Декодирование осуществляется путем перемножения кодовой комбинации С на транспонированную матрицу НТ(7,4) и вычислением указателя ошибки (синдрома S).

Вычисленный синдром S=000 указывает на то, что кодовое слово С принято без ошибки.

Предположим, что принятое кодовое слово оказалось искажен-

ным:

С*=0101001. (2.3.19)

37

Тогда

Вычисленный синдром S=101 указывает на наличие ошибки и совпадает с первым столбцом матрицы Н(7,4), что позволяет сформировать корректирующее кодовое слово (вектор) 1000000, содержащее единицу только в одном разряде, который принят с ошибкой. Это кодовое слово складывается по модулю 2 с принятой кодовой комбинацией. В результате появляется исправленная кодовая комбинация С:

0101001

1000000

1101001

Далее информационное слово I получается из кодового слова С путем отбрасывания контрольных разрядов:

Так можно обнаружить и исправить любую однократную ошибку (в любом разряде). Две или более ошибки превышают возможности корректирующего кода Хемминга, и декодер будет ошибаться.

В коде Хемминга (8,4,4) с дополнительной проверкой на четность формирование 7-разрядной кодовой комбинации аналогично формированию кода Хемминга (7,4,3). Дополнительный восьмой разряд вычисляется путем проверки 7-разрядной кодовой комбинации на четность: 0 добавляется в случае, если количество единиц в комбинации четное, 1 – если количество единиц нечетное.

Для рассмотренного выше примера кодовая комбинация 1101001 дополняется битом 0, в результате чего формируется кодовая комбинация 11010010.

38

Матрица Н(8,4,4) будет иметь вид

Декодирование осуществляется путем перемножения кодовой комбинации на транспонированную матрицу НТ(8,4,4). Синдром ошибки

Вычисленный синдром S=0000 указывает на отсутствие ошибок в принятой кодовой комбинации: С 1101001 I 1101.

Предположим далее, что кодовая комбинация принята с однократной ошибкой (в одном разряде)

С*=01010010.

Тогда