Файл: Зелигер Н.Б. Основы передачи данных учеб. пособие.pdf

ЗАВИ С И М О С ТЬ М Е Ж Д У КОЛИЧЕСТВОМ П РО ВЕРО ЧН Ы Х ЭЛЕМЕНТОВ И КРАТН О С ТЬЮ И С П Р А В Л Я Е М Ы Х О Ш И БО К

Для кода с исправлением одиночных ошибок связь между ко­ личеством проверочных элементов k и общим количеством элемен­ тов я кодовой комбинации определяется неравенством (2.25):

элементов k для исправления 7-кратных ошибок и всех ошибок

і= о

Пример. Пусть задано общее 'число элементов кодовой комбинации л=15. Требуется определить наименьшее количество проверочных элементов k, необ­ ходимое для исправления тройных ошибок, всех одиночных и всех двойных сшибок.

Для заданных условий неравенство (2.33) будет выполнено, если А=І0, ■поскольку 10 > log2 576. Приняв й=9, получим 9<log2 576, что не отвечает тре­

бованию (2.33). Количество информационных элементов т равно п—k =

= 15—10= 5.

2.5.Циклические коды

ОБ Щ И Е СВЕДЕНИЯ

Применение кодов, исправляющих одиночные и независимые многократные ошибки (двойные или тройные), не всегда оправды­ вает себя из-за возникновения в каналах связи групповых помех («всплесков»), вызывающих ошибки в рядом расположенных эле­ ментах кодовых последовательностей («пачки ошибок», «пакеты ошибок»). Поясним на следующем примере, что имеется в виду под названием «пачка ошибок».

Пусть переданная последовательность кодовых посылок запи­ шется в .виде 1 0 1 0 0 0 1 0 0 0 1 , а принятая последовательность в виде ' 10001010101. Сложение элементов этих последовательностей по мо­ дулю два дает результат: 00101000100. Мы видим, что число оши­ бок в принятой кодовой комбинации равно весу результирующей последовательности.

Длиной пачки ошибок b называется разность между старшим и младшим ошибочными разрядами принятой комбинации, увели­ ченная на единицу. В данном случае Ь — 9—3+1=7 . Обнаруже­ ние и исправление пачки ошибок наиболее эффективно осущест­ вляется циклическими и рекуррентными кодами.

69

Циклические коды обладают двумя важными свойствами. Вопервых, сумма по модулю два любых двух разрешенных комбина­ ций данного кода также является разрешенной кодовой комбина­ цией. Отсюда следует, что наименьшее кодовое расстояние в цик­ лическом коде определятся наименьшим весом его комбинаций.

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

Во-вторых, если в разрешенной кодовой комбинации осущест­ вить циклический сдвиг на один элемент, т. е. если переставить элемент комбинации, занимающий последнюю .позицию, на первое место, а все остальные элементы сдвинуть на один шаг, то в ре­ зультате получится другая разрешенная кодовая комбинация, при­ надлежащая данному коду. Например, если в коде имеется комби­ нация 1 1 0 1 0 1 , то путем циклического сдвига на один шаг получим разрешенную комбинацию 111010. Следующий сдвиг дает 01110! и т. д.

Циклические коды относятся к классу блочных: последователь­ ность кодовых посылок в них разбивается на отдельные комбина­ ции (блоки), в пределах которых производится исправление оши­ бок. Код Хемминга, исправляющий одиночные ошибки, представ­ ляет собой частный случай циклического кода. В общем случае ис­ правления многократных ошибок «-элементная кодовая комбина­ ция, отправляемая в канал, также содержит т информационных и k проверочных посылок, причем количество проверочных посы­ лок определяется кратностью ошибок, подлежащих обнаружению или исправлению.

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

ЗАП И С Ь КО ДО ВЫ Х КО М Б И Н А Ц И И В ВИДЕ ПОЛИНОМОВ

При построении циклического кода более удобным является представление последовательности кодовых посылок в виде поли­ нома от аргумента д; х заменяет основание системы счисления.

В двоичной системе счисления любое число, на основе (2.1)', может быть записано в виде полинома переменной х, коэффици­ енты; которого имеют значения іі или 0. Так, например, двоичное число 1 0 1 0 0 1 .1 0 1 , представленное в форме

101001101 =М-28 + 0-27 + 1-2в + 0-25 + 0-24 + 1-23 + 1-22 +

7 0

может быть записано в виде полинома G(x): G(x) — \-x&+ Q-x7 +

+ 1 •xe-|-l0 -x5 +{)-x4-Hl -x3+il •x2 + 0 -x1+.l -x°,

на единицу количества разрядов двоичного числа.

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

Пример.

X14- х‘ = 0 , X1+ X1+ X1= 1, —х‘ = х‘, х‘ — хі = X1+ х>, х‘''+ 0 = х‘.

ПРИ НЦ И П КО ДИ РО ВАН И Я

Пусть кодовая комбинация неизбыточного кода отображается полиномом сообщения G(x) степени (т—4), где т — число ин­ формационных посылок. Введем полином R(x), отображающий последовательность из k проверочных посылок.

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

Потребуем, чтобы кодовый полином F(x) делился на опреде­ ленный (называемый образующим) полином Р(х) степени k без остатка:

Очевидно, что условие (2.37) выполняется, если R(x) представ­ ляет собой остаток, полученный отделения xhG(x) на Р(х): '

Здесь сложение производится по модулю два, поэтому в правой части (2.38) минус заменен плюсом.

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

71

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

ПОСТРОЕНИЕ КОДА

Метод построения циклического кода базируется на соотноше­ ниях'; (2,Э6), (2.37) и (і2.38). Каждый полином сообщения G{x)r отображающий т-элементную кодовую комбинацию, умножается на одночлен хк. Далее, произведение xhG(x) делится на образую­ щий полином Р(х). Полученный в результате деления xhG(x) на Р(х) остаток R(x) определит последовательность из k провероч­ ных посылок.

Пример. Пусть двоичная запись информационных 'посылок неизбыточной m-элементной кодовой комбинации будет ilOOQlOOlOl (m =10). Соответственный полином сообщения G(x) имеет вид д ( х ) = х 9+ лг5+л:2+1. Требуется определит!, избыточную /і-элементную кодовую комбинацию циклического кода, если .известно,,

Члены кодового полинома F(x) расположены по возрастающим степеням, по­ скольку посылки кодовой комбинации отправляются в канал связи, начиная с наивысшего разряда.

Для получения всех разрешенных кодовых комбинаций цикли­ ческого (п, /ге)-кода нет необходимости в выполнении трудоемкой процедуры деления всех 2т полиномов xhG(x) на образующий по­

этого можно было бы все одночлены, отображающие строки еди­ ничной матрицы Ат, умноженные (аналогично умножению поли­ номов сообщения) на х'1, разделить на образующий полином Р(х)г затем заполнить строки дополнительной матрицы остатками от деления, отображающими проверочные элементы.

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

72