Материал: 1832

другой – 0. Затем эти вероятности складывают, результат записывают в промежутке между ближайшими вероятностями. Процесс объединения двух сообщений с наименьшими вероятностями продолжают до тех пор, пока суммарная вероятность двух оставшихся сообщений не станет равной единице. Код для каждого сообщения строится при записи двоичного числа справа налево путем обхода по линиям вверх направо, начиная с вероятности сообщения, для которого строится код [7].

редняя дл на кодового слова (табл. 2.3.6) L=2,82, что несколько меньше, чем в коде Шеннона–Фано (L=2,84). Кроме того, методика Шеннона–Фано не всегда приводит к однозначному построению кода,

2.3.5. Корректирующие коды

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

51

Наиболее распространенным является класс кодов с коррекцией одиночных и обнаружением двойных ошибок (КО–ОД). В дальнейшем речь пойдет о самом известном среди этих кодов – коде Хэмминга, который имеет простой и удобный для технической реализации алгоритм обнаружения и исправления одиночной ошибки. Построение кодов Хемминга базируется на принципе проверки на чёт-

Синость веса (числабАединичных символовДИ) в информационной группе кодового блока.

Идею представления корректирующих кодов можно представить с помощью N-мерного куба. Возьмем трехмерный куб (рис. 2.3.10), дл на ребер в котором равна одной единице. Вершины такого куба ото ражают двоичные коды. Минимальное расстояние между верш нами определяется минимальным количеством ребер, находящ хся между вершинами. Это расстояние называется кодовым обозначается буквой d.

Рис. 2.3.10. Представление двоичных кодов с помощью куба

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

Так, сложив две комбинации

10110101101

11001010101

01111111000,

определим, что кодовое расстояние между ними d=7.

Для кода с N=3 восемь кодовых комбинаций размещают на вершинах трехмерного куба. Такой код имеет кодовое расстояние d=1 и

52

для передачи используют все восемь возможных кодовых комбинаций: 000,001,..,111. Такой код не является помехоустойчивым, т.к. он не в состоянии обнаружить ошибку.

Если выберем комбинации с кодовым расстоянием d=2, например 000,110,101,011, то такой код позволит обнаруживать однократ-

ные ошибки. Назовем эти комбинации разрешенными, предназначенными для передачи информации. Все остальные 001,010,100,111 – запрещенные.

СибАДИТакой код может исправить одну одиночную ошибку или обнаружить две оши ки. Таким о разом, увеличивая кодовое расстояние,

Любая од ночная ошибка приводит к тому, что разрешенная комбинац я переход т в ближайшую запрещенную комбинацию (см. рис. 2.3.10). Получ в запрещенную комбинацию, мы обнаружим

ошибку.

Далее выберем вершины с кодовым расстоянием d=3.

можно увеличить помехоустойчивость кода. В общем случае кодовое расстояние определяется по формуле d=p+l+1, где p – число исправляемых ошибок; l – число обнаруживаемых ошибок. Обычно l>p.

Минимальным кодовым расстоянием d называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую. Если код способен исправить p ошибок, то необходимо и достаточно, чтобы d≥2p+1.

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

53

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

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

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

ошибок, одного контрольного разряда недостаточно.

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

k – кол чество основных двоичных разрядов кодового слова.

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

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

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

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

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

54

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

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

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

собой номер ош бочного разряда.

Пусть требуется передать некоторое слово 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 разря-

Таблица 2.3.9

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

55