Основы кодирования и декодирования

Размещено на http://www.allbest.ru/

Введение

Кодирование -- преобразование дискретного сообщения в дискретный сигнал, осуществляемое по определенному правилу. Обратный процесс -- декодирование -- это восстановление дискретного сообщения по сигналу на выходе дискретного канала, осуществляемое с учетом правила кодирования.

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

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



1. Непомехоустойчиыве коды

Код -- совокупность условных сигналов, обозначающих дискретные сообщения. Кодовая последовательность (комбинация) --представление дискретного сигнала. Основание кода q -- это количество признаков или число букв (цифр). Кодовая комбинация, составленная из n символов или n элементов, называется кодовым словом (кодовым блоком), имеющим длину n или число разрядов n. Если длина всех кодовых комбинаций одинакова, то такие коды называют равномерными (комплектными). Например, код 001, 011, 101 является комплектным, а код 1, 11, 101 -- некомплектным, так как слева от единиц нули не приписаны. В телемеханике обычно используют только равномерные коды. В двоичных кодах применяют также термин «вес кода», под которым понимают число единиц в кодовой комбинации. Так, вес кода 110 равен трем, а вес кода 1000 -- единице. [7]

Особенностью непомехозащищенных кодов является наличие в их составе кодовых комбинаций, которые отличаются друг от друга лишь в одном разряде. Типичным кодом такого типа является двоичный код на все сочетания. Здесь, например, комбинации 0010 и 0011 отличаются друг от друга лишь в младшем разряде. Если помеха исказит первую комбинацию, то будет принят сигнал 0011 и будет неясно, то ли принята первая искаженная комбинация, то ли вторая неискаженная. Можно найти еще ряд комбинаций в том же коде, которые отличаются друг от друга только в одном разряде. Например, комбинации 0101 и 0111 отличаются во втором разряде, комбинации 0011 и 0111 -- в третьем разряде, а комбинации 1110 и 0110 -- в четвертом разряде. Таким образом, непомехоустойчивыми (или непомехозащищенными) кодами называют коды, в которых искажение одного разряда кодовой комбинации не может быть обнаружено. Иногда их называют обыкновенными кодами.

К непомехозащищенным кодам можно отнести: двоичный код на все сочетания, единично-десятичный код, двоично-десятичный код, число-импульсный код, код Морзе, код Грея.

2. Помехозащищенные (корректирующие) коды

Помехозащищенными (или корректирующими) называются коды, позволяющие обнаружить и исправить ошибки в кодовых комбинациях. Отсюда и деление этих кодов на две большие группы: 1) коды с обнаружением ошибок; 2) коды с обнаружением и исправлением ошибок. кодовое расстояние -- это минимальное число элементов, в которых любая кодовая комбинация отличается от другой (по всем парам кодовых слов). Построение помехоустойчивого кода (а код с обнаружением ошибки является простейшим типом такого кода) связано с недоиспользованием кодовых комбинаций, приводящим к так называемой избыточности. Избыточность означает, что из исходных символов можно построить больше комбинаций, чем их применено в данном коде. Когда говорят об исправлении одиночной ошибки, считают, что вероятность двойной ошибки в канале связи пренебрежимо мала. Если такая вероятность достаточно велика, то код с d = 3 можно использовать для обнаружения двойных ошибок, но при этом исправить одиночную ошибку он уже не может. Действительно, если в нашем примере была принята комбинация 100, то нельзя утверждать, что была передана комбинация 110, так как при двойных ошибках это могла быть и искаженная комбинация 001. [1]

Таким образом, дальнейшее повышение помехоустойчивости кода связано с увеличением кодового расстояния d, что приводит к увеличению избыточности. Корректирующая способность кода зависит от кодового расстояния: а) при d=l ошибка не обнаруживается; б) при d = 2 обнаруживаются одиночные ошибки; в) при d = 3 исправляются одиночные ошибки или обнаруживаются двойные ошибки. В общем случае:



d = r + s + 1,

где d -- минимальное кодовое расстояние; r -- число обнаруживаемых ошибок; s --число исправляемых ошибок. При этом обязательным условием является r ? s. Так, в нашем примере d = 3, и если r = s = 1, то код может обнаружить одну ошибку и исправить ее. Если r = 2, s = 0, то код может только обнаружить две ошибки. Как следует из уравнения выше, для исправления одной ошибки и обнаружения двух ошибок необходимо, чтобы d = 2+ 1 + 1=4. При d = 4 может быть также вариант, когда r = 3, s = 0. Если d = 5, то могут быть три варианта: r=s = 2; r = 3, s=l; r = 4, s=0.

Если код только обнаруживает ошибки, то:

d=r + 1, т.е. r = d-1.

Если код только исправляет ошибки, то:

d = 2s+l, т. е. s=(d-1)/2.

2.1 Коды с обнаружением ошибок

Особенность этих кодов состоит в том, что кодовые комбинации, входящие в их состав, отличаются друг от друга не менее чем на d = 2. Коды с обнаружением ошибок условно можно разбить на две группы:

1) коды, построенные путем уменьшения числа используемых комбинаций;

2) коды, в которых используются все комбинации, но к каждой из них по определенному правилу добавляются контрольные m-символы. Рассмотрим сначала некоторые примеры кодов первой группы.

2.1.1 Распределительный код C_n¹

Это также разновидность кода с постоянным весом, равным единице. В любой кодовой комбинации длиной n содержится только одна единица. Число кодовых комбинаций в распределительном коде: N=C¹_n=n.

Кодовые комбинации при n = 6 можно записать в виде 000001, 000010, 000100, 001000, 010000, 100000. Сложение по модулю 2 двух комбинаций показывает, что они отличаются друг от друга на кодовое расстояние d = 2.

Рассмотрим теперь несколько примеров кодов второй группы. [1]

2.1.2 Код с проверкой на четность

Такой код образуется путем добавления к передаваемой комбинации, состоящей из k информационных символов неизбыточного кода, одного контрольного символа m (0 или 1) так, чтобы общее число единиц в передаваемой комбинации было четным. Таким образом, общее число символов в передаваемой комбинации n =k+1, так как m=1. В общем случае: n= k + m. Общее число комбинаций: N = 2^n-1. Код обладает избыточностью, так как вместо N = 2⁶=64 комбинаций может быть послано только N = 2^6-1 = 32 комбинации. В кодировании избыточность определяется отношением контрольных символов к длине слова: И= m/n

2.1.3 Код с числом единиц, кратным трем

Этот код образуется добавлением к k информационным символам двух дополнительных контрольных символов (m=2), имеющих такие значения, чтобы сумма единиц, посылаемых в линию кодовых комбинаций, была кратной трем. Он позволяет обнаружить все одиночные ошибки и любое четное количество ошибок одного типа (например, только переход 0 в 1). Не обнаруживаются двойные ошибки разных типов (смещения) и ошибки одного типа, кратные трем. На приемной стороне полученную комбинацию проверяют на кратность трем. При наличии такой кратности считают, что ошибок не было, два контрольных знака отбрасывают и записывают исходную комбинацию.

2.1.4 Код с удвоением элементов (корреляционный код)

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

Каждый элемент двоичного кода на все сочетания передается двумя символами, причем 1 преобразуется в 10, а 0-- в 01. Вместо 1010011 передается комбинация 10011001011010. Таким образом, корреляционный код содержит вдвое больше элементов, чем исходный. На приеме ошибка обнаруживается в том случае, если в парных элементах содержатся одинаковые символы, т. е. 11 или 00 (вместо 10 и 01). При правильном приеме вторые (четные) элементы отбрасываются и остается первоначальная комбинация. Код обладает высокой помехоустойчивостью, так как ошибка не обнаруживается лишь тогда, когда два рядом стоящих различных символа, соответствующих одному элементу исходной кодовой комбинации, будут искажены так, что 1 перейдет в 0, а 0-- в 1.

2.1.5 Инверсный код

В таком коде для увеличения помехоустойчивости к исходной n-разрядной комбинации по определенному правилу добавляется еще п разрядов. В результате в линию посылается удвоенное число символов. Правило образования кода следующее: если в исходной комбинации содержится четное число единиц, то добавляемая комбинация повторяет исходную, если нечетное, то в добавляемых разрядах все 0 превращаются в 1, а 1-- в 0 (комбинация инвертируется по отношению к исходной). Прием инверсного кода осуществляется в два этапа. На первом этапе суммируются единицы в первой (основной) группе символов к. Если принятое число информационных символов k четное, то контрольные символы m принимаются без изменений, если нечетное, то символы m инвертируются. На втором этапе контрольные символы m сравниваются с символами к и при наличии хотя бы одного несовпадения вся переданная комбинация n=k+m элементов бракуется. Это поэлементное сравнение эквивалентно суммированию по модулю 2. При отсутствии ошибок в обеих группах символов их сумма равна нулю. Обнаруживающие возможности инверсного кода достаточно велики. Этому, в частности, способствует метод его построения. Добавление m символов приводит к увеличению минимального кодового расстояния. После инвертирования обнаруживающие возможности кода изменяются в зависимости от числа, разрядов исходного двоичного кода. Так, если передаются все комбинации обычного двоичного кода с k= 2 (00, 01, 10 и 11), то этот непомехоустойчивый код, превращаясь в инверсный (0000, 0110, 1001 и 1111), увеличивает минимальное кодовое расстояние до d_min, = 2 и позволяет обнаруживать все одиночные ошибки и 67 % двойных ошибок.

Высокие помехообнаруживающие возможности инверсного кода достигаются за счет большой избыточности. В этом отношении инверсный код значительно уступает циклическому коду, о котором будет сказано далее. Описанный инверсный код называют также кодом с повторением и инверсией в отличие от обычного кода с повторением (без инверсии), в котором независимо от четного или нечетного числа единиц в комбинации она дополняется такой же комбинацией. Например, если вторая комбинация будет послана, как и в рассмотренном коде, т.е. 11111011111101, то третья комбинация примет вид 11111111111111. Разница между этими двумя комбинациями в двух символах (d = 2), тогда как в инверсном коде эти комбинации различаются в семи символах (d = 7). [5]

2.2 Коды с обнаружением и исправлением ошибок

Если кодовые комбинации составлены так, что отличаются друг от друга на кодовое расстояние d?3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности не только обнаруживать, но и исправлять ошибки. Составление корректирующих кодов производят по следующему правилу. Сначала определяют количество контрольных символов m, которое следует добавить к данной кодовой комбинации, состоящей из k информационных символов. Далее устанавливают место, где эти контрольные символы должны быть расставлены в комбинации, и их состав, т. е. является ли данный контрольный символ 1 или 0. На приеме обычно делают проверку на четность определенной части разрядов. [6]

2.2.1 Коды Хэмминга

Эти коды позволяют исправлять все одиночные ошибки (при d = 3), а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки (при d =4), но не исправлять их. Рассмотрим код Хэмминга, исправляющий все одиночные ошибки. В качестве исходного берут двоичный код на все сочетания с числом информационных символов k, к которому добавляют контрольные символы m. Таким образом, общая длина закодированной комбинации: n = k+ m.

Рассмотрим последовательность кодирования и декодирования по Хэммингу.

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

Таким образом, может быть n + 1 вариантов искажения (включая передачу без искажений). Используя контрольные символы, необходимо различить все n+ 1 вариантов. С помощью контрольных символов m можно описать 2^m событий. Значит, должно быть выполнено условие: 2^m ? n+1 = k+m+1. Размещение контрольных символов. В принципе место расположения контрольных символов не имеет значения: их можно приписывать и перед информационными символами, и после них, и чередуя информационные символы с контрольными. Однако произвольное расположение контрольных символов затрудняет проверку принятого кода. Для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т. е. на позициях 1, 2, 4, 8 и т. д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для семиэлементной закодированной комбинации можно записать: m₁, m₂, k₄, m₃, k₃, k₂, k₁. Определение состава контрольных символов. Какой из символов должен стоять на контрольной позиции (1 или 0), выявляют с помощью проверки на четность. В табл. 1 записаны все кодовые комбинации (исключая нулевую) для трехразрядного двоичного кода на все сочетания и рядом справа, сверху вниз проставлены символы комбинации кода Хэмминга, записанные в последовательности, которую мы составили выше.

Таблица 1 Составление проверочной таблицы для кода Хэмминга

Разряды двоичных чисел	Символы кода
3(k3)	2(k2)	1(k1)
0	0	1	m1
0	1	0	m2
0	1	1	k4
1	0	0	m3
1	0	1	k3
1	1	0	k2
1	1	1	k1

Таблица 2 Проверочная таблица для кода Хэмминга

m1	k4	k3	k1
m2	k4	k2	k1
m3	k3	k2	k1

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

Так, в комбинациях 001, 011, 101 и 111 единицы находятся в младших разрядах, поэтому в первой строке табл. 2 записывается символ m₁, против которого стоит единица. Контрольный символ m₂ не записывается в первую проверку, так как число 010 в младшем разряде содержит не 1, а 0. Далее в первую строку записывается символ k₁, так как комбинация 011 на конце содержит 1. Символ m₃ в первую строку не записывается, так как комбинация 100 в первом разряде содержит 0. В первую строку табл. 2 запишутся символы k₃ и k₁ вследствие того, что комбинации 101 и 111 в первом разряде имеют единицы. [1]

Во вторую строку проверочных коэффициентов (табл. 2) записываются символы, против которых проставлены единицы во втором разряде двоичного кода. Так, комбинации 010, 011, 110 и 111 содержат во втором разряде 1, поэтому вторая строка проверочных коэффициентов состоит из символов m₂, k₄, k₂ и k₁.

В третью строку записываются символы, против которых проставлены единицы в третьем разряде двоичного кода (m₃, k₃, k₂ и k₁). В случае кодирования более длинных кодовых комбинаций табл. 3.10 и 3.11 должны быть расширены, так как должны быть записаны четвертая, пятая и т. д. строки проверочных коэффициентов. Для этого нужно лишь увеличить число разрядов двоичного кода в табл.1. Так, для комбинации m₁, m₂, k₄, m₃, k₁₀, k₈, k₄, m₄, k₇, k₆, k₅, k₄, k₃, k₂, k₁ табл. 2 будет состоять из четырех строк. Число проверок, а значит, и число строк в табл. 2 равно числу контрольных символов m. Состав контрольных символов с помощью проверок определяют следующим образом. Суммируют информационные символы, входящие в каждую строку табл. 2; если сумма единиц в данной строке четная, то значение символа m, входящего в эту строку, равно 0, если нечетная, то 1. По первой строке табл. 2 определяют значение символа m₁, по второй -- m₂, по третьей -- m₃. [3]

Декодирование. Для проверки правильности комбинации снова используют метод проверки на четность. Если комбинация принята без искажения, то сумма единиц по модулю 2 даст нуль. При искажении какого-либо символа суммирование при проверке может дать единицу. По результату суммирования каждой из проверок составляют двоичное число, указывающее на место искажения. Например, первая и вторая проверки показали наличие искажения, а суммирование при третьей проверке дало нуль. Записываем число 011=3, которое означает, что в третьем символе кодовой комбинации, включающей и контрольные символы (счет производится слева направо), возникло искажение, поэтому этот символ нужно исправить на обратный ему, т. е. 1 на 0 или 0 на 1. После этого контрольные символы, стоящие на заранее известных местах, отбрасывают. При проверках принятой комбинации возможны следующие варианты: 1) ошибок нет (прием верен); это показывает, как общая проверка на четность, так и частные проверки (для рассматриваемого кода частных проверок три), в процессе которых m_доп отбрасывается; 2) одиночная ошибка; общая проверка на четность показывает наличие ошибки (сумма единиц по модулю 2, входящих в кодовую комбинацию, не дает нуль), а частные проверки комбинации без разряда m_доп указывают на номер искаженного символа (нулевое значение числа, полученное в результате проверки, свидетельствует об искажении в дополнительной контрольной позиции); 3) две ошибки; общая проверка на четность указывает на отсутствие ошибок, а частные проверки -- на наличие ошибок (указывается номер позиции, где якобы возникла ошибка, однако ее не следует исправлять, а лишь констатировать наличие двух ошибок).

Добавление дополнительного контрольного символа к закодированной для исправления одиночной ошибки кодовой комбинации увеличивает кодовое расстояние с d = 3 до d = 4, так как r = 2, s=l, a d = 2 + 1 + 1=4.

Рисунок 1 Принципиальная электрическая схема кодера Хэмминга



Рисунок 2 Принципиальная электрическая схема декодера Хэмминга

Рисунок 3 Полная принципиальная схема кода Хэмминга

Переключатели 1…8 имитируют информационные биты передаваемых данных. С помощью четырёх логических элементов Исключающее ИЛИ D1…D4 формируются контрольные биты k₁, k₂, k₄, k₈. В канал связи передаётся 12 бит (восемь информационных и четыре контрольных бита). Четыре логических элемента DP1…DP4 производят расчёт контрольных битов на приёме. Следующие четыре логические схемы Исключающее ИЛИ DSS1…DSS4 вычисляют синдром. Значение синдрома в шестнадцатеричной СС отображается на индикаторе H1. Если индикатор показывает нуль, то это означает, что передача данных произошла без искажений.

При наличии сбоев в канале связи показания индикатора изменяются от 1 до CH. Данная конструкция приёмника только указывает номер искажённого разряда, но коррекции принятых данных не производит. [4]

2.2.2 Циклические коды

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

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

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

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

Методы построения циклических кодов. В качестве информационных символов к для построения циклических кодов берут комбинации двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию Q(X) умножить на образующий многочлен Р(Х), получится циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора Р(Х). Однако в этом коде контрольные символы т будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце кода, т.е. после информационных символов. Для этой цели целесообразно воспользоваться следующим методом.

1. Умножаем кодовую комбинацию G(X), которую мы хотим закодировать, на одночлен Х^m, имеющий ту же степень, что и образующий многочлен Р(Х).

2. Делим произведение G(X)X^m на образующий многочлен Р(Х^m):

G(X)X^m / Р(Х^m) = Q(X) + R(X) / P(X),

где Q(X) -- частное от деления; R(X) -- остаток. Умножая предыдущее выражение на Р(Х) и перенося R(X) в другую часть равенства, согласно правилам алгебры двоичного поля, т.е. без перемены знака на обратный, получаем: F(X) = Q(X)Р(Х) = G(X)X^m + R(X).

Таким образом, циклический код, т. е. закодированное сообщение F(X), можно образовать двумя способами:

1) умножением одной из комбинаций двоичного кода на все сочетания [комбинация Q(X) принадлежит к той же группе того же кода, что и заданная комбинация G(X)] на образующий многочлен Р(Х);

2) умножением заданной кодовой комбинации G(X) на одночлен Х^m, имеющий ту же степень, что и образующий многочлен Р(Х), с добавлением к этому произведению остатка R(X), полученного после деления произведения G(X)X^m на образующий многочлен Р(Х).

Циклические коды, обнаруживающие одиночную ошибку (d =2).

Код, образованный многочленом Р(Х)=Х+1, обнаруживает не только одиночную ошибку, но и любое нечетное число ошибок. Предположим, что необходимо закодировать сообщение G(X) = Х³ + Х² + 1 -->1101 с помощью образующего многочлена Р(Х) = Х+1->11. Умножим G(X) на Х^m что эквивалентно добавлению нуля справа, так как m=1, поскольку Р(Х) имеет первую степень: (Х³+ Х²+ 1)Х = X⁴+Х³ + Х--> 11010. Разделив полученное выражение на Р(Х), найдем, что остаток R(X)= 1. Следовательно, кодовый многочлен циклического кода будет иметь вид:

F(X) = G(X)X^m + R(X)=X⁴ + X³ + X + 1= 11010 + 1 = 11011.

Таким образом, в этом закодированном сообщении 11011, n = 5, k = 4 и m = 1, т.е. информационным символом является комбинация 1101, а контрольным -- единица в младшем разряде. Сообщение, которое было закодировано (1101), является одной из 16 комбинаций четырехразрядного кода. Если требуется передать все эти сообщения в закодированном виде, то каждое из них следует кодировать так же, как и комбинацию 1101. Однако проделывать дополнительные 15 расчетов нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы. Образующая матрица составляется из единичной транспонированной матрицы и матрицы дополнений. Число столбцов транспонированной единичной матрицы равно числу информационных символов k. Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен Р(Х), выраженный в двоичном эквиваленте. Число остатков равно числу информационных символов.

Как следует из результатов деления единицы с нулями на Р(Х)=Х+ 1->11, все остатки оказываются равными единице. Поэтому образующая матрица имеет вид:



Рисунок 4 Образующая матрица для циклического кода

Четыре кодовые комбинации, из которых состоит образующая матрица, являются первыми кодовыми комбинациями циклического кода. Пятая комбинация нулевая, а так как в четырехразрядном непомехозащищенном коде всего N = 24= 16 комбинаций, то остальные 11 ненулевых комбинаций находят суммированием по модулю 2 всевозможных комбинаций строк образующейматрицы:

Рисунок 5 Пример образующей матрицы и суммирование ненулевых комбинаций

Сгруппируем полученные комбинации следующим образом:

Рисунок 6 Группировка комбинаций

Видно, что в первом столбце от комбинации к комбинации две рядом стоящие единицы сдвигаются на один символ влево, во втором столбце циклически сдвигаются две единицы, не стоящие рядом друг с другом, а в третьем столбце происходит циклический сдвиг четырех единиц. Этот циклический сдвиг одной комбинации по отношению к другой и определил название кодов -- циклические. Заметим, что циклический сдвиг является результатом умножения кодовой комбинации на Х. Действительно, вторую комбинацию можно записать как 00101 -> X² + 1, седьмую -- как (X² + 1)Х = X³ + X -> 01010 и т. п. Если при умножении на X степень становится равной Х^m-1, то полученный результат нужно разделить на X+ 1. Например, если комбинацию 10101=X⁴+X²+1 умножить на Х, то получим X⁵+Х³+X. Для полученного выражение на Х⁵+1, найдем остаток X³+X+1->01011. Многочлен 01011 и является результатом циклического сдвига на один разряд влево многочлена 10101. [10]

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

Циклические коды с d = 3. Эти коды могут обнаруживать одиночные и двойные ошибки или обнаруживать и исправлять одиночные ошибки.

1.Выбор числа контрольных символов. Есть два способа выбора числа m. При первом способе исходят из того, что число контрольных символов

m = n - k зависит от числа информационных символов, а значит, и от длины всей кодовой комбинации. Выбор m производится, как и для кода Хэмминга, с исправлением одиночной ошибки:

m=E''log₂[(n+1)],

где E'' - знак округления в большую сторону.

При втором способе число контрольных символов m определяется по эмпирической формуле:



m=E''log₂[(k+1)+ E''log₂(k+1)].

2. Выбор образующего многочлена Р(Х). Степень образующего многочлена 1 не может быть меньше числа контрольных символов m. Это значит, что если m = 3, то можно выбрать любой образующий многочлен Р(Х) начиная с третьей степени и выше. Для упрощения технической реализации кодирования степень Р(Х) следует выбирать равной числу m, т. е. 1 = m. Если в таблице имеется ряд многочленов с данной степенью, то из них следует выбрать самый короткий. Однако число ненулевых членов многочлена Р(Х) не должно быть меньше кодового расстояния d.

3. Нахождение элементов дополнительной матрицы.

Дополнительную матрицу находят путем деления единицы с нулями на выбранный многочлен R(X) и выписывания всех промежуточных остатков. При этом должны быть соблюдены следующие условия:

а) число остатков должно быть равно числу информационных символов к;

б) для дополнительной матрицы пригодны лишь остатки с весом W, не меньшим числа обнаруживаемых ошибок r, т. е. в данном случае не меньшим 2 (W>2); так обнаруживается не менее двух ошибок.

Из условий а) и б) определяется количество нулей, приписываемых к единице при делении ее на многочлен Р(Х);

в) так как элементы дополнительной матрицы являются для данной комбинации контрольными символами, то число разрядов дополнительной матрицы равно числу контрольных символов т. Вследствие того, что степень образующего многочлена выбирают равной от, число разрядов дополнительной матрицы равно также степени образующего многочлена. Например, если m = 3, а остаток равен 11, то он должен быть записан как 011. Из сказанного вытекает, что разрядность остатка равна степени образующего многочлена.[11]

4. Составление образующей матрицы. Берут транспонированную единичную матрицу и справа приписывают к ней элементы дополнительной матрицы. Пример составления образующей матрицы был дан при рассмотрении циклического кода с обнаружением одиночной ошибки.

5. Нахождение всех комбинаций циклического кода данной группы. Это достигается суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы, как было показано при рассмотрении циклического кода с обнаружением одиночной ошибки.

Циклические коды с d=4.

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

1. Выбор числа контрольных символов. Число контрольных символов в

этом коде должно быть на единицу больше, чем для кода с d = 3:

m_d=4=1+log₂(n+1)

2. Выбор образующего многочлена. Образующий многочлен P(X)d=4 равен произведению двучлена (Х+1) на многочлен Р(Х)_d=3:

Р(Х)_d=4=(X+1)Р(Х)_d=3

Это объясняется тем, что двучлен (Х+1) позволяет обнаружить все одиночные и тройные ошибки, а многочлен Р(Х) -- двойные ошибки. В общем случае степень / многочлена Р(Х)_d=4 = 4 равна числу m. Дальнейшая процедура

кодирования остается такой же, как и при образовании кода с обнаружением двойной ошибки.[1]

Циклические коды с d ?5.

Эти коды, разработанные Боузом, Чоудхури и Хоквинхемом (сокращенно коды БЧХ), позволяют обнаруживать и исправлять любое число ошибок. Заданными при кодировании является число ошибок s, которое следует исправить, и общее число символов, посылаемых в линию, т. е. длина слова n. Числа информационных символов к и контрольных символов т. а также состав контрольных символов подлежат определению.

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

1. Выбор длины слова. При кодировании по методу БЧХ нельзя выбирать произвольную длину слова n. Первым ограничением является то, что слово может иметь только нечетное число символов. Однако даже при этом не все нечетные числа могут составлять длину слова. Здесь могут быть два случая:

1) по заданному n находят такое число h чтобы удовлетворялось равенство: 2^h-1=n. Например, при n = 7 h = 3, при n=15 h = 4, при n= 31 h = 5, при n = 63 h = 6 и т. д.;

2) находят такое число h, чтобы удовлетворялось равенство: (2^h-1)/g=n, где h>0-целое число, а g - нечетное положительное число, при делении на которое n получается целым нечетным числом.

2. Определение кодового расстояния. Кодовое расстояние определяют:

d = 2s + 1.

3. Определение образующего многочлена Р(Х). Образующий многочлен есть наименьшее общее кратное (НОК) так называемых минимальных многочленов М (X) до порядка 2s-1 включительно, причем образующий многочлен составляется из произведения некоторого числа нечетных минимальных многочленов:

P(X)=НOK[M₁(X)M₃(X)...M_2s-1(X)]…

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

4. Определениечисла минимальных многочленов L. Из уравнения следует, что порядок минимальных многочленов определяется как 2s-1. Если учесть, что этот образующий многочлен состоит только из нечетных минимальных многочленов, то число их определяется просто. Например, если s = 3, то 2s-1=5. Это значит, что в уравнении будут записаны минимальные многочлены М₁(Х), М₃(Х) и М₅(Х), т. е. L = 3. Если s = 8, то 2s-1 = 15 и в уравнении будут использованы минимальные многочлены М₁(Х), М₃(Х), М₅(Х), М₇(Х), М₉(Х), М₁₁(х), М₁₃(Х), М₁₅(Х), т. е. L=8. Таким образом, число минимальных многочленов равно числу исправляемых ошибок: L=s.

5. Определение старшей степени l минимального многочлена. Степень l есть такое наименьшее целое число, при котором 21-1 нацело делится на n или ng, т. е. n= 2l-1 или 2l'-- 1 =ng. Отсюда следует, что l=g.

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

7. Определение степени р образующего многочлена РB(Х). Степень образующего многочлена зависит от НОК и не превышает произведения ls или lL, так как L = s.

Таблица 3 Минимальные многочлены циклических кодов

8. Определение числа контрольных символов. Так как число контрольных символов m равно степени образующего многочлена, то в коде длины n:

B= m ?ls.

9. Определение числа информационных символов. Его производят обычным порядком из равенства k = n-m. Дальнейшие этапы кодирования аналогичны рассмотренным для циклических кодов с d<4. T. е. находят дополнительную матрицу, составляют образующую матрицу, по которой рассчитывают все кодовые комбинации.[3]

Рисунок 7 Принципиальная электрическая схема кодера циклического кода

Рисунок 8 Принципиальная электрическая схема декодера циклического кода



2.2.3 Коды БЧХ и Файра

Их строят следующим образом. Если необходимо образовать код с обнаружением четного числа ошибок, то по заданному числу r находят значения d и s. Дальнейшее кодирование выполняют, как и ранее. Если требуется обнаружить нечетное число ошибок, то находят ближайшее меньшее целое число s и кодирование производят так же, как и в предыдущем случае, с той лишь разницей, что найденный образующий многочлен дополнительно умножают на двучлен (Х+1). Например, требуется построить код БЧХ, обнаруживающий семь ошибок при n=15. Находим, что d=8, а ближайшее меньшее значение s=3. Далее определяем многочлен Р(Х), и умножаем его на двучлен (Х+1), т.е. получаем Р(Х)=Х¹¹ + X¹⁰ + X⁹ + X⁸ + X⁶ + Х⁴+ +Х³+ 1. Таким образом построен код БЧХ.[2]

Циклические коды, обнаруживающие и исправляющие пакеты ошибок (коды Файра). Под пакетом ошибок длиной b понимают такой вид комбинации помехи, в которой между крайними разрядами, пораженными помехами, содержится b -- 2 разряда. Например, при b = 5 комбинации помехи, т. е. пакет ошибок, могут иметь следующий вид:

10001 (поражены только два крайних символа), 11111 (поражены все символы), 10111, 11101, 11011 (не поражен лишь один символ), 10011, 11001, 10101 (поражены три символа). При любом варианте непременным условием пакета данной длины является поражение крайних символов. Коды Файра могут исправлять пакет ошибок длиной b_s и обнаруживать пакет ошибок длиной b_r (заметим, что в кодах Файра понятие кодового расстояния d).

Образующий многочлен кода Файра Р(Х)ф определяется из выражения:

радиосвязь сигнал код цифровой

P(X)_ф=P(X)(X^c-1),

где P(X) - неприводимый многочлен степени l.

Из прицнипа пострения кода следует, что l ?b;

c ?b_s+b_r-1, при этом с не должно делиться нацело на число е, где e=2^l-1

Неприводимый многочлен Р(Х) выбирают из таблицы многочленов. Длина слова n равна наименьшему общему кратному чисел с и е, так, как только в этом случае многочлен Xⁿ + 1 делится на Р(Х)_ф без остатка [при n'<n никакой многочлен Xⁿ' +1 не делится на Р(Х)_ф: n = НОК(е,с)

Число контрольных символов m = с + 1.

Декодирование циклических кодов. Обнаружение ошибок. Идея обнаружения ошибок в принятом циклическом коде заключается в том, что при отсутствии ошибок закодированная комбинация F(X) делится на образующий многочлен Р(Х) без остатка. При этом контрольные символы m отбрасываются, а информационные символы к используются по назначению. Если произошло искажение принятой комбинации, то эта комбинация F(X) преобразуется в комбинацию Н(Х), которую можно представить, как сумму двух многочленов:

H(X)=F(X) +Е(Х),

где Е(Х) -- многочлен ошибок, содержащий столько единиц, сколько элементов в принятой комбинации не совпадает с элементами переданной комбинации. [5]

Пусть, например, была передана комбинация кода F(X)= = 1101001, закодированная с помощью Р(Х)=1011. Если она принята правильно, то деление на Р(Х) даст остаток, равный нулю. Если же комбинация принята как Н(Х)= 1101011, то при делении на Р(Х) образуется остаток 010, что свидетельствует об ошибке, и принятая комбинация бракуется.

Обнаружение и исправление ошибок. Существует несколько вариантов декодирования циклических кодов. Один из них заключается в следующем.

1. Вычисление остатка (синдрома). Также, как и в кодах с обнаружением ошибок, принятую комбинацию делят на образующий многочлен Р(Х). Остаток R(X) = 0 означает, что комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Дальнейшая процедура исправления ошибок протекает таким образом. [7]

2. Подсчет веса оста т к a W. Если вес остатка равен или меньше числа исправляемых ошибок, т. е. W ?S то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.

3. Циклический сдвиг на один символ влево. Если W>s, то производят циклический сдвиг на один символ влево и полученную комбинацию снова делят на образующий многочлен. Если вес полученного остатка W ?S, то циклически сдвинутую комбинацию складывают с остатком и затем циклически сдвигают ее в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получают исправленную комбинацию.

4. Дополнительные циклические сдвиги влево. Если после циклического сдвига на один символ по-прежнему W>s, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига сдвинутую комбинацию делят на Р(Х) и проверяют вес остатка. При W ?s выполняют действия, указанные выше, с той лишь разницей, что обратных циклических сдвигов вправо делают столько, сколько их было сделано влево.



Заключение

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

Главным отличием блоковых кодов от сверточных является отсутствие наличия памяти у первых. Термин "без памяти" указывает, что каждый блок из n символов зависит только от соответствующего блока из k символов и не зависит от других блоков. Для каждого кода есть своя определенная методика кодирования и декодирования. Также в этой работе были промоделированы схемы для кода Хэмминга и циклических кодов в электронной программе WorkBench 5.1, MatLab 2017.



Список использованной литературы

1. Тутевич В. Н. Т 91 Телемеханика: Учеб. пособие для студентов вузов спец. «Автоматика и телемеханика». -- 2-е изд, перераб. и доп.-- М.: Высш. шк., 1985. -- 423 с, ил.

2. Боуз Р.К., Рой-Чоудхури Д.К. Об одном классе двоичных групповых кодов с исправлением ошибок // Кибернетический сборник. - 1961. - Вып. 2. - С. 83-94.

3. Берлекэмп Э.Р. Техника кодирования с исправлением ошибок // ТИИЭР. - 1980. - Т. 68, № 5, - С. 24-58.

4. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. - М.: Вильяме 2003. - 1104 с.

5. Вернер М. Основы кодирования. -- М.: Техносфера, 2004.

6. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.

7. Мальцев, Ю.Н. Введение в дискретную математику. Элементы комбинаторики, теории графов и теории кодирования / Ю.Н. Мальцев, Е.П. Петров. - М.: [не указано], 1997. - 319 c.

8. Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса. - М.: Техносфера, 2006. - 320 c

9. Рихтер, С. Г. Кодирование и передача речи в цифровых системах подвижной радиосвязи / С.Г. Рихтер. - М.: Горячая линия - Телеком, 2011. - 304 c.

Размещено на Allbest.ru

...