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

Для определения необходимости применения корректирующего кода в проектируемой системе рассчитаем вероятность ошибочного приема комбинации.

Вероятность ошибочного приема одного символа определяем из исходных данных на дипломное проектирование: .

Общее количество комбинаций, формируемых двоичным кодом, определяется формулой:

,

где k количество информационных символов комбинации. Таким образом, можно рассчитать количество символов комбинации:

, , .

Вероятность ошибочного приема 7-элементной комбинации рассчитаем по формуле:

.

Согласно исходным данным на проектирование вероятность ошибочного приема комбинации не должна превышать величины 0,005. Таким образом, необходимо использовать какие-либо методы повышения достоверности передачи.

Одним из наиболее эффективных методов повышения достоверности является использование корректирующих кодов. Рассмотрим эти коды подробнее.

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

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

Широкое распространение на практике получили такие исправляющие коды, как коды Хэмминга и циклические коды. Рассмотрим эти коды подробнее.

Принцип построения кодов Хэмминга и их характеристики рассмотрим на примере одной из разновидностей: кода, исправляющего одиночные ошибки.

Комбинация кода содержит k информационных символов и q проверочных. Проверочная группа формируется таким образом, чтобы при проверке принятой комбинации на достоверность (в процессе декодирования) можно было бы указать номер разряда, в котором произошла ошибка. Это достигается с помощью многократных проверок принятой комбинации на четность, количество которых равно количеству проверочных символов q. Каждой проверкой (суммированием по модулю два) охватывается часть информационных символов и один из проверочных символов. В результате каждой проверки получают двоичный контрольный символ. Если результат проверки четное число, то контрольному символу присваивается значение 0, если нечетное число - 1. По окончании всех проверок получается q-разрядное двоичное контрольное число (синдром проверки), которое указывает номер ошибочного символа в принятой комбинации. Для исправления ошибки значение этого символа изменяют на обратное.

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

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

В таблице 2 помещены номера искаженных символов, представленные в двоичной форме.

Таблица 2

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

Следовательно, первая проверка должна охватывать все нечетные символы:

(2.1)

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

Следовательно, вторая проверка должна охватывать именно эти символы:

(2.2)

Аналогично третья и четвертая проверки должны выглядеть следующим образом:

(2.3)

(2.4)

В качестве проверочных символов удобно выбрать такие, которые входят в минимальное число проверок. Такими символами являются символы

При кодировании значение каждого проверочного символа устанавливается таким, чтобы сумма единиц в соответствующей проверяемой группе являлась четным числом, то есть П1=П2=П3=П4=…=0.

Число проверочных символов выбирается в соответствии с таблицей 2 для кодового расстояния б=3

. (2.5)

Представим в качестве примера двоичную безызбыточную комбинацию 1001 кодом Хэмминга. При к =4 неравенство (2.5) выполняется, если q =3. Следовательно, вся комбинация кода Хэмминга должна состоять из 7 символов. Значения информационных символов заданы: а₃=1, a₅ =0, а₆ =0, а₇ =1. Определяем в соответствии с (2.1) - (2.4) значения проверочных символов: а₁=0, а₂=0, а₄=1. Итак, комбинация кода Хэмминга имеет вид 0011001. Допустим, что шестой разряд комбинации принят с ошибкой, то есть принята комбинация 00110011. Тогда в результате первой проверки получим 0, во второй проверке 1, в третьей 1. Контрольное число 110 указывает на то, что шестой символ принят неправильно.

На рисунке 12 представлен один из возможных вариантов функциональной схемы кодирующего устройства кода Хэмминга (7/4).

Рисунок 12

Схема включает в себя три сумматора по модулю два, осуществляющие формирование проверочных символов а₁, а₂, а₄. Исходная безызбыточая комбинация поступает на входы кодирующего устройства в параллельном коде.

На рисунке 13 представлен вариант функциональной схемы декодирующего устройства кода Хэмминга (7/4). В устройство входят три сумматора по модулю два, осуществляющие проверочное суммирование, дешифратор ошибки на три входа и четыре выхода и схема, исправляющая ошибку, состоящая из сумматоров по модулю два. Дешифратор имеет 4 выхода, а не 7 потому, что исправлению подлежат только информационные символы. Цифровые обозначения на рисунке соответствуют рассмотренному примеру декодирования комбинации, в которой имелась одна ошибка в шестом разряде (обозначена жирно).

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

Число разрешенных комбинаций кода Хэмминга

. (2.6)

Избыточность кода

. (2.7)

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

. (2.8)

Рисунок 13

Вероятность ошибочного приема кодовой комбинации

. (2.9)

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

. (2.10)

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

. (2.11)

Сравнивая помехоустойчивость кода Хэмминга, обнаруживающего двукратные ошибки, и кода с четным числом единиц, можно убедиться в том, что эти коды обеспечивают приблизительно одинаковую вероятность обнаруживаемой ошибки, вероятность же необнаруживаемой ошибки у кода Хэмминга значительно меньше, чем у кода с четным числом единиц (при Р_ош=10^-3 более чем на два порядка).

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

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

(2.12)

гдеn - количество символов в кодовой комбинации, представляемой многочленом (значность кода);

x - фиктивная переменная;

а₀, а₁, а₂, … коэффициенты, принимающие значения 0 или 1.

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

и .

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

(2.13)

Приведем здесь определение циклических кодов [l6], которое основано на представлении двоичных кодов в виде многочленов: циклическим (n, k) кодом называется код, множество кодовых комбинаций которого представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый образующий многочлен р (x) степени q=n-k.

Исходя из этого определения, для формирования комбинации циклического кода F (x) достаточно исходную комбинацию безызбыточного кода G (x) умножить на образующий многочлен p (x)

(2.14)

Однако этот способ приводит к образованию неразделимого кода, что усложняет процесс декодирования.

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

Способ заключается в следующем. Сначала исходный многочлен G (x) умножают на х^q, сдвигая тем самым все информационные символы комбинации на q разрядов влево и освобождая "место" в младших разрядах для проверочных символов. В двоичной форме умножение числа на х^q равносильно приписыванию справа q нулей. Затем полученное произведение делят на образующий многочлен р (х) и находят остаток от деления R (x) степени меньшей q, то есть

(2.15)

где Q (x) - целая часть частного.

Искомый многочлен циклического кода имеет вид:

(2.16)

Здесь информационные символы представлены коэффициентами при x в степени q, и выше, а проверочные коэффициентами при x в степени q-1 и ниже. Многочлен (2.16) представляет разрешенную комбинацию циклического кода и в соответствии с определением делится на образующий многочлен р (х) без остатка.

Действительно,

(2.17)

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

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

Таблица 3

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

(2.18)

В таблице 3, заимствованной из [16], представлены все неприводимые многочлены до шестой степени включительно и некоторые многочлены от седьмой до десятой степени.

Рассмотрим в качестве примера процессы кодирования и декодирования циклическим кодом, содержащим к =4 информационных символов и имеющим кодовое расстояние б =3, то есть исправляющим однократные или обнаруживающим двукратные ошибки.

Для обеспечения б =3 кодовая комбинация должна содержать q =3 проверочных символа. При этом значностъ кода n=k+q=4+3=7. Из таблицы 3 выбираем образующий многочлен

p (x) = x³+x+1.

Предположим, что необходимо закодировать комбинацию 1011. Комбинации соответствует многочлен G (x) = x³+x+1. В соответствии со вторым из рассмотренных способов кодирования умножим этот многочлен на x³

x³G (x) = x⁶+x⁴+x³.

Разделим x³G (x) на р (х) и найдем остаток R (x)

Остаток R (x) = x². Искомый многочлен F (x) = x³G (x) +R (x) =x⁶+x⁴+x³+x², что соответствует двоичной комбинации 1011100.

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

Остаток, отличный от нуля, свидетельствует о наличии ошибки в принятой комбинаций. В рассматриваемом примере остаток может состоять из трех элементов (максимальная степень R (x) равна 2), которые в зависимости от номера искаженного символа образуют одну из семи комбинаций, не считая нулевой 000. Следовательно, по виду остатка можно определить номер любого из 7 символов принятой комбинации, который окажется искаженным, и внести исправления.

Кодирующее устройство циклического кода состоит из двух основных узлов, один из которых обеспечивает умножение исходного многочлена на x^q, а во втором производится деление произведения x^qG (x) на P (x).

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

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

На рисунке 14 представлены функциональные схемы регистров с обратными связями, соответствующие различным неприводимым многочленам Р (х). Регистры содержат q ячеек (степень многочлена Р (x)) и (z-1) встроенных сумматоров по модулю два, где z количество членов многочлена Р (х).

На каждую ячейку регистра подаются тактовые импульсы. На схеме эти цепи не показаны. Если записать многочлен P (x), начиная с младшего члена, перед которым поставить знак плюс, и старший член вместе со знаком плюс отбросить, то местоположение сумматоров по модулю два на функциональной схеме будет определяться этой записью. Сумматор для сложения старших разрядов многочлена P (x) и последовательности информационных символов не нужен, так как результат сложения старших разрядов делимого и делителя равен нулю (2.19).

P (x) =x²+x+1

P (x) = x³+x²+1

P (x) = x⁴+x+1

Рисунок 14

На рис.15 представлена схема кодирующего устройства циклического кода (7/4) с образующим многочленом P (x) =x³+x²+1.

Рисунок 15

Схема работает следующим образом. Информация на вход кодирующего устройства поступает в последовательном коде. Для деления многочлена x^qG (x) в рассматриваемом примере требуется 7 тактов. В течение первых трех тактов оба регистра заполняются информационными символами (эта операция эквивалентна умножению G (x) на x^q). Затем в течение последующих 4 тактов происходит деление информационной последовательности на образующий многочлен, и на выход поступают все 4 информационных символа комбинаций. Ключ 1 при этом закрыт, а ключ 2 открыт.

Остаток R (x) от деления многочлена x^qG (x) на образующий многочлен фиксируется на элементах регистра-делителя. Далее ключ 2 закрывается, разрывая обратную связь и исключая влияние выхода регистра на его вход, а ключ 1 открывается. (С этого момента регистр-делитель превращается в обычный сдвигающий регистр, в котором записан остаток R (x)). В течение последних тактов на выход кодирующего устройства поступает остаток R (x). Таким образом, на выход кодирующего устройства поступает вся 7-разрядная комбинация, состоящая из первых 4 информационных и последующих 3 проверочных символов.

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

H (x) =F (x) +E (x), (2.20)

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

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

На рисунке 16 представлено декодирующее устройство циклического кода (7/4), исправляющего однократные ошибки (n=7, k=4, q=3). Принимаемая комбинация H (x) в течение 7 тактов записывается в запоминающий регистр и одновременно делится на образующий многочлен P (x) =x³+x²+1. Ключ закрыт. В результате деления при наличии в принятой комбинации искаженного символа в регистре-делителе будет зафиксировано двоичное трехразрядное число, равное остатку от деления многочлена H (x) на P (x). По виду этого остатка определяется номер искаженного информационного символа в комбинации.

Рисунок 16

Однократная ошибка в 7-разрядной кодовой комбинации может описываться одним из семи многочленов ошибок E (x):

1000000 E (x) =x⁶ - ошибка в первом разряде;

0100000 E (x) =x⁵ - ошибка во втором разряде;

…………………………………………………….

0000010 E (x) =x - ошибка в шестом разряде;

0000001 E (x) =1 - ошибка в седьмом разряде.

(В данном случае первый разряд является старшим, седьмой младшим). При делении многочленов ошибок на P (x) имеет место следующее однозначное соответствие многочленов ошибок и остатков от деления:

1000000 110; 0010000 111

0100000 011; 0001000 101

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

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

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

Допустим, что после деления получился остаток 011 (искажен второй символ в принятой комбинации). Процессы, происходящие в регистре-делителе во время 8-то такта, удобно рассмотреть с помощью таблицы 4.

Таблица 4

В таблице в строке против цифры 7 отображено состояние элементов памяти регистра-делителя после 7 тактов (записан остаток 011). В первых двух строках против цифры 8 отображены переходные процессы, происходящие в элементах памяти и цепи обратной связи регистра-делителя в течение 8-го такта. Последняя строка свидетельствует о том, что в регистре-делителе остается записанной комбинация 110, которая дешифрируется с приходом 9-го такта и из запоминающего регистра выводится искаженный символ, который и исправляется.