Королёв А.И. Коды и устройства помехоустойчивого кодирования

Подождите немного. Документ загружается.

А.И. Королев

КОДЫ И УСТРОЙСТВА ПОМЕХОУСТОЙЧИВОГО

КОДИРОВАНИЯ ИНФОРМАЦИИ

Минск 2002

УДК 621.391.14:621.394

К38

Рецензент:

Белоусов В.П. – кандидат технических наук

Королев А.И.

К38. Коды и устройства помехоустойчивого кодирования информации. – Мн.:

Бестпринт , 2002. – с.286

ISBN 987-7336-77-1

Рассматриваются способы задания групповых линейных блоковых и

сверточных кодов, а также принципы построения кодеков данных кодов, реа-

лизующие алгебраические и вероятностные алгоритмы декодирования. Боль-

шое внимание уделяется вопросам аппаратурной реализации кодеков цикличе-

ских и сверточных кодов корректирующие как независимые, так и пакетные

ошибки.

Для инженерно-технических работников и студентов электро и радио-

технических вузов.

ISBN 987-7336-77-1 © А.И. Королев, 2002

ПРЕДИСЛОВИЕ

В настоящие время обеспечение высокой достоверности передачи, обра-

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

электросвязи. Эффективным способом решения данной проблемы является ис-

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

Преднамеренное введение избыточной информации в передаваемые информа-

ционные сообщения обеспечивает возможность обнаружения и исправления

ошибок на приемной стороне.

Математическая теория построения избыточных (помехоустойчивых) ко-

дов в настоящие время имеет большие достижения. Однако существует боль-

шой разрыв между уровнем теоретических достижений теории помехоустой-

чивого кодирования и уровнем результатов практического использования дан-

ной теории. Широкому применению результатов теории помехоустойчивого

кодирования в современных системах связи, обработки и хранения информации

следует считать отсутствие достаточно простых решений сложных теоретиче-

ских достижений теории помехоустойчивого кодирования.

В данной книге кратко излагается теоретические сведения о групповых

линейных блоковых и сверточных кодах, а также рассматриваются вопросы

разработки структурных и функциональных схем кодеков данных кодов, реали-

зующих различные алгоритмы декодирования.

Книга будет полезна студентам электро и радиотехнических вузов, а так-

же инженерно-техническому персоналу, разрабатывающие и обслуживающие

системы передачи, обработки и хранения информации.

СПИСОК ОСНОВНЫХ СОКРАЩЕНЫХ ОБОЗНАЧЕНИЙ

АС – анализатор синдрома

АСП – анализатор синдромной последовательности

АЧХ – амплитудно-частотная характеристика

АВ – алгоритм Витерби

АФ – алгоритм Фано

БАС – блок анализатора синдрома

ДШ – дешифратор синдрома

ДФСК – диффузные сверточные коды

ДФССК – диффузные самоортогональные сверточные коды

КРВ-1/k

– коммутатор распределения ветвей (подпотоков): одного потока дво-

ичных символов на k

≥2) подпотоков

КРВ-1/n

– то же, на n

+1) подпотоков

КОВ-k

/1 – коммутатор объединения k

ветвей (подпотоков) в один поток дво-

ичных символов

КОВ-n

/1 – то же, n

подпотоков в один поток двоичных символов

ПД – пороговое декодирование

ПИ – передача информации

ПФ – полосовой фильтр

СК – сверточный код

ССК – самоортогональной сверточный код

СБЛК – систематический блоковый линейный код

ФПС

к(д)

– формирователь проверочных символов (к – кодер д - декодер)

ФЧХ – фазо-частотная характеристика

ЦК – циклический код

1. ВВЕДЕНИЕ В ИСТОРИЮ РАЗВИТИЯ ТЕОРИИ И ПРАК-

ТИКИ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ. ХА-

РАКТЕРИСТИКИ КОДОВ. КЛАССИФИКАЦИЯ КОДОВ

1.1. Направления исследований помехоустойчивого кодирования и их

краткая характеристика

История возникновения и развития теории и практики избыточного

(помехоустойчивого) кодирования информации, с целью коррекции ошибок и тем

самым обеспечения требуемой достоверности передачи информации (ПИ)

началась с 1946 г., а именно, после публикации монографии американского

ученого Шеннона, а именно «Работы по теории информации и кибернетике».

В данной работе Шеннон доказал, что если скорость ПИ (В, бит/с) меньше

пропускной способности какала связи (С, бит/с), то есть В < С, то можно

подобрать такой избыточный (помехоустойчивый) код и способ кодирования

информации данным кодом (алгоритм декодирования не рассматривался), при

котором может быть обеспечена сколь угодно малая вероятность ошибочного

приема информации. Шеннон также показал в этой работе, что построение

каналов связи с очень хорошими характеристиками является дорогостоящим

мероприятием, а экономически выгоднее использовать избыточное, т.е.

помехоустойчивое кодирование. Однако Шеннон не указал как построить

помехоустойчивые коды, а лишь доказал их существование. Следует заметить,

что результаты работы Шеннона базировались на работах советских ученых:

Хинчина, Колмогорова, Харкевича, Варшамова и др.

Установим, что понимается под термином «пропускная способность канала

связи» и «скорость ПИ». Суть понятий в следующем:

- пропускная способность канала связи (С) – определяется как максимальное

число переданных двоичных единиц (двоичных символов, битов) в секунду при

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

(бита), которая в принципе может быть сколь угодно малой;

- скорость ПИ (В) – это реально переданное число двоичных символов (битов)

в установленную единицу времени (в секунду) и при заданной равной

вероятности ошибочного приема двоичного символа (бита).

Пропускная способность канала связи и скорость передачи информации

измеряются в бит/с, Кбит/с, Мбит/с и Гбит/с.

При неограниченно малой вероятности ошибок на двоичный символ

скорость ПИ всегда меньше пропускной способности канала связи, т.е. В<C. В

канале связи с ошибками максимальное значение скорости ПИ может быть

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

Однако при этом следует иметь в виду:

а) если помехоустойчивый код согласован с характеристиками канала связи,

т.е. позволяет исправлять наиболее вероятные ошибки, то введенная

избыточность информации становится оправданной;

б) если же помехоустойчивый код не будет согласован с характеристиками

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

размножены кодом.

После выхода из печати работы Шеннона десятки ученых и сотни

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

кодирования и уже на конец 1948 г. можно отметить, что теория и практика

помехоустойчивого кодирования развивалась по двум направлениям [1...3].

Первое направление носило чисто алгебраический характер и в основном

рассматривались способы построения блоковых (блочных) кодов и алгоритмы их

декодирования.

Первые два блоковых кода (n

) = (7,4,3) и (n

) =

(7,3,4) были

открыты (построены) Хэммингом в 1947 г., а также им была разработана теория

построения линейных блоковых кодов. Хэмминг ввел и дал определение

основным параметрам (характеристикам) блоковых кодов, а также разработал

кодирующее (кодер) и декодирующее (декодер) устройства для своих кодов. Для

оценки корректирующей способности кодов Хэмминг ввел параметры кодовое (d)

и минимальное кодовое (d

) расстояния и показал их зависимость от длины кода и

от вводимой избыточности. В честь больших заслуг Хэмминга перед теорией и

практикой помехоустойчивого кодирования параметры d и d

носят название

соответственно хэмминговое и минимальное хэмминговое расстояние.

В 1949 г. Абрамсон предложил ещё два блоковых кода, а именно (n,k,d

) =

(15,10,5) и (n,k,d

) = (10,5,5); при построении данных кодов в основном

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

Хэммингом. Данные коды, как и коды Хэмминга, оказались очень слабыми по

корректирующей способности по сравнению с обещанными Шенноном кодами.

Несмотря на усиленные исследования до конца 50-х годов (до 1959 г.) не было

найдено и построено лучшего класса кодов, чем коды Хэмминга и Абрамсона. В

эти же годы, а точнее с 1949 по 1959 гг., без какой-либо общей теории были

открыты многие блоковые коды и неблоковые коды, в том же числе, так

называемые непрерывные или цепные коды; данные коды были предложены в

1954 г. одновременно Элайсом и Финком.

Основной сдвиг в теории помехоустойчивого кодирования произошел в

конце 50-х годов и в начале 60-х годов, а именно, когда в 1959 г. Хоквингейм, а в

I960 г. Боузе и Чоудхури предложили теорию построения линейных блоковых

кодов, корректирующие как независимые ошибки, так и пакетные ошибки. Эти

коды получили название БЧХ-кодов.

В 1960-61 гг. Рид и Соломон независимо друг от друга разработали теорию

построения линейных блоковых кодов, корректирующие пакетные ошибки и

группирующиеся пакеты ошибок, при этом кодирование информации может быть

выполнено как в двоичном поле Галуа GF(2), так и в недвоичном поле Галуа

GF(2

), m≥2. Эти коды получили название кодов Рида-Соломона или РС-кодов.

Несмотря на то, что коды БЧХ и PC-коды оставались очень важными среди

всех кодов, общая теория построения блочных групповых кодов продолжала

успешно развиваться и время от времени удавалось открывать новые коды.

Так в 1964 г. Прейндж предложил теорию построения циклических кодов

(ЦК) существенно упростивших как алгоритм кодирования, так и алгоритм

декодирования групповых кодов. В 1966 г. Файр предложил теорию построения

ЦК, корректирующих одиночные пакеты ошибок произвольной кратности

(длины), измеряемой в двоичных символах. В 1967 г. Форни, Блох и Зяблов

разработали теорию построения каскадных кодов, корректирующие

одновременно как независимые ошибки, так и пакетные ошибки.

Второе направление исследований по помехоустойчивому кодированию

носило вероятностный характер. Первоначально исследования были связаны с

оценками вероятностей ошибки для лучших классов блоковых кодов; хотя эти

лучшие коды ещё не были открыты. Эти исследования проводились с целью

понять помехоустойчивое кодирование и декодирование с вероятностной точки

зрения.

Данные исследования привели к открытию алгоритмов последовательного

декодирования применительно к классу древовидных кодов, которые относятся к

классу сверточных кодов (СК), которые в свою очередь, являются дальнейшим

развитием непрерывных кодов.

В 1967 г. Витерби разработал для СК эффективный вероятностный алгоритм

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

С 1970 г. эти два направления исследований вновь стали пересекаться , в том

плане, что теорией построения СК занялись математики-алгебраисты,

представившие теорию построения СК в новом математическом изложении.

В теории блоковых кодов были получены коды, на которые указывал

Шеннон; были предложены два способа построения помехоустойчивых кодов

(первый способ - Юстессена, а второй – способ Гоппы), позволяющих строить

классы кодов, которые одновременно могут иметь очень большую длину блока

кодовой последовательности и очень хорошие параметры кода (R,r,d

). Но оба

этих способа построения кодов имеют ограниченное практическое применение в

виду их высокой сложности реализации.

1.2. Области применения помехоустойчивого кодирования

Развитие помехоустойчивого кодирования первоначально стимулировалось

задачами электросвязи, а поэтому многие термины теории помехоустойчивого

кодирования взяты из теории электросвязи. Однако в настоящее время

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

техники. Например, в системах обработки информации (в системах ЭВМ), в

устройствах памяти ЭВМ, в системах записи на магнитные ленты (МЛ), диски

(МД), компакт-диски, в БИС и СБИС и т.д. Помехоустойчивое кодирование

используется в системах управления ракетами, в системах сжатия информации и

т.д.

Применение помехоустойчивого кодирования к задачам электросвязи в

настоящее время имеет самый различный характер. Например, помехоустойчивое

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

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

Кроме того, поскольку электромагнитный спектр все больше и больше

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

с заданным качеством (достоверностью) при наличии межсимвольных искажений

(МСИ). В военных системах связи помехоустойчивое кодирование часто

применяют для защиты информации против преднамеренных помех. Очень

важным является применение помехоустойчивого кодирования в спутниковых

системах связи (ССС), так как помехоустойчивое кодирование позволяет

уменьшить Р

/Р

на входе приемника спутника связи (СС) и тем самым

уменьшить вес спутника связи (СС) и, следовательно, уменьшить стоимость

запуска СС, либо оставив вес СС прежним можно увеличить его функциональные

возможности.

Очень важным является применение помехоустойчивого кодирования в

системах и сетях ЭВМ, так как в таких системах и сетях даже одиночные ошибки

могут нарушить программу вычислений.

Очень важным и эффективным является применение помехоустойчивого

кодирования в системах записи информации на МЛ, МД, так как это позволяет

увеличить плотность записи информации на 1 мм

площади носителя информации

и, следовательно, записать больший объем информации.

Эффективное применение помехоустойчивое кодирование может найти в

системах управления (автопилоты, цифровые системы управления ракетами,

самолетами и т.д.), в радарных системах как воздушного, так и наземного

базирования, в медицинских системах, в локальных сетях (ЛС) и т.д.

1.3. Современные направления развития теории и практики помехо-

устойчивого кодирования

В каком направлении надо сейчас работать исследователю в теории и

практике помехоустойчивого кодирования? В соответствии с [1,2] ответ таков –

это зависит от выбранного критерия оценки эффективности помехоустойчивого

кодирования.

Так если взять в качестве критерия минимальную сложность алгоритмов

кодирования и декодирования кодов и их реализацию и, следовательно,

минимальную стоимость, то хорошим кодом может считаться помехоустойчивый

код, имеющий "хороший" алгоритм декодирования (минимальную сложность

алгоритма, минимальную задержку информации при декодировании, коррекцию

ошибок больше теоретической корректирующей способности и т.д.). Инженер-

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

максимальное значение d

, если неизвестен хороший алгоритм декодирования.

"Хорошие" помехоустойчивые коды нуждаются в хороших декодерах, а

"хорошие" алгоритмы декодирования найти трудно. Найти "хороший" алгоритм

декодирования сейчас также важно, как и найти "хороший" код.

Поиск теоретиками новых кодов, допускающих использование известных

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

поиск новых алгоритмов декодирования для известных кодов: (последний вывод

является спорным).