Введение в теорию кодирования информации

 

                                             a5= а1+а2+a3,

                                             a6= а2+а3+a4

                                             a7= а1+а2+a4,

 

Линейные коды бывают систематическими (разделенными) и  несистематическими (неразделёнными). Если известно местоположение (безразлично, на каких позициях они расположены) проверочных и информационных разрядов, то такой код называют систематическими (разделенным). В несистематических (неразделенных) кодах все символы являются кодовыми символами. Как правило, коды, используемые в цифровой обработке сигналов, являются неразделёнными. Нелинейные коды отличаются от линейных кодов тем, что для них не выполняется одна или ряд аксиом группы        

 

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

 

     Сверточный кодер обычно представляется в виде регистра сдвига, и многие основные определения могут быть введены с использованием такой схемы. Рассмотрим кодер, представленный на рис.5. Информационная последовательность вводится в кодер, начиная с нулевого момента времени и до бесконечности. Поток входящих информационных символов разбивается на сегменты, которые содержат по k₀ символов и называются кадрами информационных символов. Кадр информационных символов может, в частности, состоять из единственного символа, что нередко имеет место на практике. В кодере может храниться т кадров. В течение каждого временного кадра в регистр сдвига вводится новый кадр информационных символов, а кадр информационных, символов, дольше остальных хранившийся в нем, выводится из него и сбрасывается. В конце каждого временного кадра в кодере хранятся последние т из поступивших в него кадров (всего тk₀ информационных символов). В начале каждого временного кадра кодер по введенному кадру информационных символов и т хранящимся в нем кадрам вычисляет один кадр кодового слова, имеющий длину n₀ символов. Этот кадр кодового слова выводится из кодера, как только поступает следующий кадр информационных символов. Следовательно, каждым k₀ информационным символам соответствует передача по каналу n₀ кодовых символов.

     Бесконечное множество всех бесконечно длинных кодовых слов, получаемых при поступлении в этот кодер всех возможных входных последовательностей, называется древовидным(n₀,k₀)-кодом.

    Формальное определение древовидного кода. Древовидный(n₀,k₀)-код - это такое отображение на себя множества полубесконечных последовательностей элементов изGF(q), что если для любого М первые Мk₀ компонент двух полубесконечных последовательностей совпадают, то первые М n₀ компонент отображений этих последовательностей тоже совпадают. Древовидный код лучше всего можно представить себе, обратившись к кодеру, изображенному на рис. 5.

 

 

                                           Рис. 5.Сверточный кодер

 

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

Конечность  длины кодового ограничения. Длина кодового ограничения - у=тко может быть конечной или бесконечной. Практически древовидные коды всегда имеют конечную длину кодового ограничения. Однако в теоретических исследованиях иногда полезны коды с бесконечной длиной кодового ограничения. Древовидный (щ, /с₀)-код с конечной длиной кодового ограничения V, длиной слова к=у+к₀ и кодовой длиной блока п называется также решетчатым (и, к)-кодом.

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

Линейность. Кодовая последовательность любой линейной комбинации двух информационных последовательностей совпадает с такой же линейной комбинацией кодовых последовательностей этих двух информационных последовательностей. Иначе говоря, если й\, и йг являются двумя информационными последовательностями с кодовыми последовательностями и 0(а^,₂), то ао?, +М₂ соответствует кодовая

последовательность

С (да/, + М_г) = ав (</,) + ЪО (о?₂).

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

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

Линейный постоянный во времени древовидный (ио, #о)-код, имеющий конечн}-!© длину слова к=(п + 1) ко, называется сверточным (п, к)-кодом. Сверточный (л, &)-код, удовлетворяющий условию систематичности, называется систематическим сверточным (п, к)-кодом. Известно, что можно называть один и тот же код древовидным (и₀> &о)-кодом или сверточным (п, /с)-кодом. На практике к значительно больше к₀, и поэтому недоразумений не возникает. Постоянный во времени древовидный (п₀, ко)-код, имеющий конечную информационную длину слова к, называется скользящим блоковым (и, к)-кодом. Следовательно, линейный скользящий блоковый код является сверточным кодом.

На рис. 7.2 графически показаны связи между различными классами древовидных кодов.

с

                                   Рис. 7.2. Классификация древовидных кодов

Основными характеристиками сверточных кодов являются: «   ко - размер кадра информационных символов;

• щ - размер кгдра кодовых символов;

• т — длина памяти кода;

• к= (т+1) ■  к₀ - информационная длина слова;

• п = (т+1) ■ «о - кодовая длина блока - это длина кодового слова, на которой сохраняется влияние одного кадра информационных символов;

• К = к1п - скорость, которая характеризует степень избыточности кода, вводимой для обеспечения справляющих свойств кода.

На рис. 7.1. изображен  кодер, у которого /со=3, гс_и=5, у=21, «=40. Кодовая длина блока - это длина кодового слова, на которой сохраняется влияние одного кадра информационных символов. Из соображений удобства реализации на практике значения щ и /с₀ для древовидных кодов выбираются равными небольшим целым числам; в типичном случае ко равно единице. Это означает, что выбор скорости кода ограничен. Невозможно построить практический древовидный код со скоростью, очень близкой к единице.

7.1.2. Описание  сверточных кодов с помощью  многочленов и матриц

Сверточный ((т-И)по, (/я+1)А^,₀)-код над СР^) с длиной кодового ограничения у=т/с₀ можно генерировать с помощью наборов фильтров с конечной импульсной характеристикой (КИХ-фильтров); каждый набор состоит из к₀ КИХ-фильтров над ОР(д). Поэтому последовательность на выходе кодера можно рассматривать как свертку импульсной характеристики кодера с входной последовательностью. Импульсная переходная характеристика фильтра (ИПХ) (а кодер сверточного кода, по сути дела, является фильтром) есть реакция на единичное воздействие вида 6=

(10000.....). Рассмотрим примеры  кодирования последовательностей  с

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

Пусть т = (ПО ... , тогда для кодера с импульсной переходной характеристикой Я = (11.00.00.01.00.00....___

и- 11.00.00.01.00.00...

11.00.00.01.00... (7= 11.11.00.01.01.00.00... ,

т =(1011000...)

 ГУ= П.ОО.ОО.01.00.00.00...

11.00.00.01.00...

__ 11.00.00.01...

[/=11.00.11.10.00.01.01.00....

На рис. 7.3. показан  кодер для двоичного сверточного  кода с гсо=5 и ко=\. В кодер поступает поток символов со скоростью ко символов в единицу времени, а из него выходит в канал поток символов со скоростью щ символов в единицу времени.

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

                      

8.1. Построение  низкоскоростных кодов 8.1.1. Общие  сведения о низкоскоростных кодах

К низкоскоростным кодам относятся коды, у которых количество проверочных символов значительно превышает количество информационных символов и, соответственно, скорость передачи мала. Однако низкоскоростные коды характеризуются значительным кодовым расстоянием а^п/2. Поэтому также коды корректируют примерно четверть ошибок на длине п и занимают особое положение в теории и практике помехоустойчивого кодирования. Следует отметить, что для большинства из них разработаны эффективные алгоритмы формирования и декодирования. С точки зрения теории кодирования они являются классическими кодами, с другой стороны, свойства кодов позволяют использовать их в качестве основы для формирования таге называемых сложных сигналов для систем связи, синхронизации, локации, навигации, систем передачи и криптографической залшты информации. Под сложными обычно понимают такие сигналы, для которых произведение их длительности на занимаемую полосу частот значительно больше единицы. Помимо термина «сложный» сигнал часто используется понятие широкополосного сигнала (в зарубежной литературе кх называют сигналами «срастянутым спектром» (зргеас1 зрес1шт)).

Ня практике находят  применение как отдельные кодовые  слова низкоскоростных кодов, так и их ансамбли. В радиотехнических системах со сложными кодированными сигналами на передающей стороне к каждому отсчету передаваемы}; данных ставится в соответствие своя дискретная псевдослучайная последовательность, спектр частот которой значительно превышает полосу данных. Отдельные кодовые слова рассматриваются как кодовые последовательности символов щ,     и_п.\). Поэтому большое

значение имеют периодические и апериодические корреляционные свойства кодовых последовательностей. Периодическая автокорреляционная функция двоичной последовательности 1/\ определяется следующим образом

где   т = 0,1,...,и -1, а  сумма 1 + 1 берется по модулю п.

Ансамбли кодовых последовательностей используются для формирования систем сигналов, обладающих оптимальными корреляционными свойствами при кодовом разделении сигналов различных абонентов, использующих для передачи информации общий канал. Определяющим в синтезе ансамбля является критерий минимума боковых выбросов автокорреляционных функций и минимума значений взаимокорреляционных функций, который находится для пары последовательностей и={«_;} и у = {у,} следующим выражением

;=о

К низкоскоростным кодам принадлежат  последовательности Холла, Якоби, квадратично-вычетные и характеристические последовательности, а также М-последовательности и коды на их основе (коды Голда, Кассами и др.), последовательности Гордона-Милса-Велча.

 

 

 

 

8.1.2. Формирование низкоскоростных кодов

Формирование кодов максимальной длины

Коды максимальной длины являются наиболее изученными низкоскоростными кодами. Отдельные кодовые слова данных кодов называют М-последовательностями. Двоичные М-последователъности - класс кодовых последовательностей, используемых для формирования сигналов с идеальными автокорреляционными свойствами (боковые выбросы всегда равны -1). Коды максимальной длины представляют собой примитивные БЧХ-коды, имеющие следующие параметры: и = 2^к -1, й = 2^к~~^х, I = 2^к~^г -1. М-последовательности, являющиеся .шнейными циклическими кодами, обладают свойством периодичности: {",} = {«;+,,}• Подстановка К:г' = /,-, (/,и) = 1 переводит М-последовательность саму в себя либо в последовательность другой формы. Общее число различных последовательностей определяется формулой

М = ф)/к, где    ф(и) - функция Эйлера числа п.

Обычно М-последовательности формируются при помощи линейных автоматов, описываемых проверочными - А(х) и генераторными - §(х) полиномами. Если для построения генератора используется проверочный полином, то его основу составляет операция деления на Н(х). Из к символов, формирующих начальный блок символов, образуют полином, который после умножения на х" является делимым. Полином частного образует формируемую М-последовательность. Например, для информационного блока (1001) информационный полином равен х* +1, когда после его умножения на х¹⁵ образуется полином х^и +х¹⁵, который при последующем