Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 20
Текст из файла (страница 20)
2.6. Постоянный симметричный канал. Регулярное кодироаание Наибольшее распространение среди регулярных кодов получили систематические коды„ вопросы построения которых рассматриваются в алгебраической теории кодирования, пользующейся аппаратом современной алгебры (!1, !2, 431 Систематический (п, А) код представляет собой набор п-разрядных кодовых комбинаций, к которых А разрядов (обычио первые) представляют собой результат примитивного кодирования сообщения. Они называютси информационными разрядами.
Остальные и — А разрядов образуются по определенным правилам из информационных, они называются проверочными (корректирующими) и служат для обнаружения и исправления ошибок. Так, например, код (7.4) — это код, в котором ссмиэлементиая кодовая корби~нация содержит 4 информационных символа. Другими славами, процесс кодирования сообщения можно представить последовательностью двух процессов — сначала производится кодирование равномерным А-разрядным кодом без внесения избыточности, а затем к каждой кодовой комбинации приписываются сформированные по определенным правилам и — А корректирующих разрядов. Количество допустимых кодовых комбинаций в систематическом коде равно Ф,=сна. Отсюда легко определить избыточность кода г,=! — =1 — — '=е1 — — = —.
(2.49) В (у) 1оя Л', (с и — У Пмвнс (у) И зУ Корректирующие символы формируются с помощью линейных операций, определенных над конечным полем и производимых над информационными символами. В частном случае, когда пч — простое число, эти операции совпадают с операциями сравнений по модулю пт 1171 Напомним, что целые числа Я и В называются 100 сравнимыми по модулю кч (записывается, А= — В(пзоблз)), если оба эти числа при делении |на кч дают одинаковый остаток. Так, например,5— = 11 (шос(3) нли 8=— 15(шос(7). Для формирования корректнрукяцих символов производится сложение по модулю т определенных информационных символов (представленных числами от О до т — 1). Это зчзачит, что произведя арифметическое сложение указанных чисел, сумму заменяют наименьшим целым неотрицательным числом, сравнимым с этой суммой по модулют (или «наименьшим вычетом по модулю пз»).
Так, например, 1+2= — 0 (гпоб 3), 2+2= — 1 (зяб 3) 1+1= — 0 (гпос1 2) и т. д. Очевидно, что в результате таких операций получа- ются числа от 0 до гп — 1,которые могут представлять корректирующие символы"'. Выбирая надлежащим об- разом уравнения, по которым формируются корректи- рующие символы, можно построить код с заданным ми- нимальным хсмминговым расстоянием с(„,„ь Не вдаваясь в подробности теории корректирующих кодов, которая весьма обстоятельно изложена в мо- нографии (1!), приведем пример построения кода (7,4) при гп=2. Как видно из обозначения, 4 разряда кодо- вой комбинации заняты информационными символами.
Обозначим их а, аь а„ а,. Остальные 3 разряда заня- ты корректирующими символами, которые обозначим Ьь Ьа, Ьз. Символы а, мокнут принимать значения 0 или 1, определяемые кодируемым сообщением. Символы Ьс оп- ределяются уравнениями а,+аз+а,+Ь,=О, а, + а, + а, + Ь, =- О, (2.50) а,+а,+а,+܄—.О, где слонсения производятся по модулю 2. Так, напри- мер, если информационными символами являются 1001, с Заметим, что в быту мы часто пользуемся оаожеиием по модулю 24 (илп 12) при отсчете времеви. Таа, если сейчас 19 чпс, то через !О чос будет 5 час утра.
Зер(сзщпельио, 19+(0=5 (изоб 24). 101 то корректирующими должны быть 110. В таком коде д „„=3. В этом легко убедиться, если заметит>я что замена значения одного нз информационных символов на противоположное влече~ за собой замену значений по меньшей мере двух корректирующих сч.>волов, а замена значений каких-либо двух из информационных символов неминуемо приводит к замене значения по крайней мере одного корректирующего символа. Поэтому .любые две допустимые 1т. е. удовлетворяющие уравнениям (2.50)) кодовые комбинации отличаются друг от друга не менее чем в трех разрядах.
Отсюда следует, что, используя такой код, можно всегда оГ>наруживать ошибку, если ошибочно принято не более двух символов в комбинации, либо исправлять ошибку, если ошибочно принят один символ. С целью обнаружения ошибок принятая кодовая комбинация подвергается проверке на удовлетворение уравнениям использованным для формирования корректирующих символов". Если хотя бы одно из этих уравнений не удовлетворено, то принятая комбинация не принадлежит к числу допустимых и, следовательно, в процессе передачи произошла ошибка.
При исправлении ошибок ~необходимо учитывать, какие из уравнений пе удовлетворены, н руководствоваться опецнальиымн правиламп, легко устанавливаемыми для конкретного кода. Например, если из уравчепяй (2.50) два оказываются справедливыми, а одно пе удовлетворяется, то ошибочно принятым следует считать один из корректирующих символов и принятая комбинация может быть декодирована поинфариацпанпым символам без каких-либо исправлений.
Еш>и не удовлстворены первые два уравнения, то подлеясит исправлению (замене 0 на 1 или 1 па 0) символ аз, который входит в оба эти уравнения. Если не удовлетворены 1-е н 3-е уравнения, то испрпвлеппю подлежит символ аь Если не удав,четворспы 2-е и 3-е уравнения, то исправлению подлежит символ во Наконец, если все три уравнения пе удовлгтворены, то исправлению падле>кит символ аз. Конечно, если в кодовой комбинации оши- ' В случае даоичиык корректиру>осипа колею зти прививки иазыв:ос ироюрколи ни >егиость, поскольку аыражеиис Э' х, ааО (тес) 2) озиачает попросту, что зта сумма ивлистси зстиым числом. 102 бочно приняты два или более символов, то такая комбпнацня не будет правильно декодирована. Рассмотрим нскоторыс алгебраические свойства двоичных систематических кодов, позволяющие подробнее исследовать их обнаруживающую и исправля>ащую способность Двоичный систематический код, содержащий комбинацию, состоящую пз одних нулей, образует абелеву группу относительно операции поразрядного сложения по модулю 2.
Это значит, что сложив по модулю 2 символы, находящиеся в одинаковых разрядах двух разрешенных кодовых ках>бнпацпй, мы получим также разрешенную комбинацию. Поэтому такие коды называют также групповыми. Групповой код можно одяозначно определить, задав всего лишь й входящих в него линейно независимых комбинаций.
Они образуют производящую матрш)у 6, имеющую й строк и и столбцов. По ней можно построить все остальные кодовые комбинации, складывая (поразрядно по модулю 2) попарно, по три, по четыре и т. д. с~роки производящей матрицы. В частности, складывая любую строку саму с собой получим нулевую комбинацию (состоящую из п нулей). Для рассмотренного выше кода (7,4) производящая матрица ма>кот быль записана, например, в таком виде: 1000101 0100111 0010110 0001011 В памяти кодера достаточно иметь производящую матрицу.
С помощью устройства поразрядного суммирования можно получить любую кодовую комбинацию. Для декодирования с обнаружением или исправлением ошибок в памяти декодера достаточно хранить проверачярра лсатрицу Л>, содержащую п — А строк и п столбцов. В каждой строке этой матрицы единлцы находятся в тех разрядах, которые входят в соответствующее проверочное уравнение" (2.50). В нашем прим! ере " П оизве еи, ро>зведеиие производище)1 матрицы иа транспонированную проверочку>о з>ат)и>иу равно пулю. 1ОЗ >>! о! оо о>>!о>о >>о>оо! Таким образом, ,при систематическом коде объем памяти кодера и декодера растет не экспоненциально с увеличением и, а только пропорционально >г' (учитывая, что й пропорционально и).
Тем нс менее количество операций, которые нужно проделать для декодирования с исправлением ошибок, а следовательно, и сл,»кность декодера растут приблизительно экспоненциально, хотя и с меньшим показателем, чем при случайном кодировании. В последние годы особое внимание привлекает разновидность систематических кодов, называемых циклическими. Они отличаются тем свойством, что всякая циклическая перестановка символов разрешенной кодовой комбинации приводит также к разрешенной комбинации. Эта особенность, а также некоторые алгебраические свойства циклических кодов позволяют существенно упростить схемы кодирования и декодирования !11, 14, 18).
Для некоторых циклических кодов возмсокна сравнительно простая (хотя и пе всегда оптимальная) процедура декодирования, называемая нажо1>итарным или пороговы>я декодированием (13, 19). Среди циклических кодов, предназначенных для постоянного симметричного канала, наилучшими явля>отся коды с особой алгебраическон структурой, называемые кодами Боуза — Чоудхури. Для любых целых з и 1 существует код Боуза — Чоудхури, исправляющий все ошибки кратностью Г (т. е. имеющий с( „=21+1) при п=2' — 1 и й)2" — 1 — яг. Так, например, для з=б и 1=3 получим код с п=63, й)45 и п>я,„,=7. Введение циклических кодов сделало возможным построение кодеров и декодеров для и порядка нескольких десятков при исправлении ошибок и порядка соген при обнаружении ошибок.
Такие коды с различной избыточностью позволяют обеспечить довольно высокую верность приема в реальных каналах. Тем не менее в ряде случаев желательно применять еще более длинные коды с возможно более простым устройством декодера. Поэтму не прекращаются изыскания новых методов построения кодов, Здесь следует упомянуть о рабо- >О> те Р, Галлагера (20), предло>кившего систематичсскпй код, построение проверочной матрицы которого содержит на одном из этапов случайный выбор.
Поэтому такой код нельзя считать полностью ре~улярным. Благодаря тому, что строки и столбцы проверочной матрицы содержат значительно меньше единиц чем нулей, этот код допускает относительно простую процедуру декодирования. Весьма перспективным являются свергочные коды, для которых разработан метод последовательного декодирования [10). Их обычно относят к случайным кодам, однако в их построении имеется элемент регулярности, который и позволяет упростить процесс декодирования. Все рассмотренные и упомянутые коды являются блочными.
Существу>от также и непрерь>внь>е коды, в которых последовательность передаваемых симво.чов нельзя разделить на отдельные блоки. В качестве примера опишем один из рекдрренгнь>х кодов, называемый >!епныг> (!4, 21) и отличающийся предельно простыми методами кодирования и декодирования. В частности, он допускает мажоритарное декодирование. Как уже указывалось, в этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
