Материал: 1740
|
106 |
|
|
Лабораторная |
Код с проверкой на четность и цик- |
работа 7 |
лический код |
1.Введение
Вцифровых системах связи широко применяются корректирующие коды, т.е. коды, способные обнаруживать и исправлять ошибки, возникающие в канале с шумом. Особенно часто используют коды с однократной проверкой на четность и циклические коды с кодовым расстоянием, равным трем.
Цель настоящей работы – изучение принципов построения кодера и декодера, а также экспериментальное исследование корректирующей способности кодов на примере кода с проверкой на четность (7,6) и циклического кода (7,4).
2.Сведения из теории корректирующих кодов
2.1. Общие сведения
В дискретных каналах с шумом передача символов сопровождается случайными ошибками. Основным способом повышения помехоустойчивости системы передачи информации (СПИ) в этих условиях является разумное введение избыточности в передаваемый сигнал.
Идея рационального введения избыточности в передаваемый сигнал реализуется применением корректирующих кодов. Наиболее часто применяют блочные корректирующие коды. Информационная кодовая комбинация (КК) с выхода источника сообщений содержит k разрядов a=a1, a2,…, ak, где ai=0;1. Считается, что она не имеет избыточности. Будем рассматривать только двоичные коды (основание кода m=2). Число всех возможных КК от источника N=mk=2k. В пространстве двоичных КК вводят понятие расстояния Хэмминга. Расстоянием Хэмминга dij называет число символов, в которых кодовые комбинации ai и aj отличаются друг от друга. Для двоичного кода расстояние dij удобно определять как вес (количество единиц) кодовой ком-
107
бинации, полученной в результате суммирования ai и aj по модулю два (mod 2). Суммирование по mod 2 выполняется по правилу
0 0=0, 0 1=1, 1 0=1, 1 1=0. (7.1)
Вес КК равен количеству единиц, содержащихся в ней.
Для кодов, использующих в качестве разрешенных все N=2k кодовых комбинаций, минимальное значение расстояния равно единице. Такие коды называют безызбыточными. Они не позволяют обнаруживать и исправлять ошибки, возникающие в канале связи. Для осуществления коррекции ошибок вводят избыточность:
1)в виде r лишних, избыточных символов; тогда длина КК увеличивается и становится равной п=k+r. При этом избыточность кода оценивают как R=r/п;
2)выделением из общего числа N кодовых комбинаций Np разрешенных, используемых для передачи. Остальные Nз=N–Np комбинаций являются запрещенными. Величина избыточности
равна R (log N з ) /(log N ). Ошибки в канале связи обычно (но
не обязательно) переводят разрешенную КК в запрещенную и таким образом обнаруживаются.
Отличие (расстояние) между переданной и принятой КК называют кратностью ошибки q. Корректирующие коды могут обнаруживать и даже исправлять некоторые ошибки, возникающие при передаче по каналу связи. Для характеристики корректирующих свойств кода вводят понятие кодового расстояния, т.е. минимального расстояния Хэмминга для данного кода
dкод=min dij, |
i j. |
(7.2) |
При грамотном введении избыточности в передаваемый |
||
сигнал минимальное расстояние |
увеличивается и |
становится |
dкод>l. Связь между кратностью обнаруживаемой ошибки qo, кратностью исправляемой ошибки qи и величиной кодового расстояния определяется так:
dкод qo+1, |
dкод 2qи+1. |
(7.3) |
Таким образом, для обнаружения любой однократной |
||
ошибки (qo=1) корректирующий |
код должен иметь |
хотя бы |
dкод =2, а для исправления любой однократной ошибки (qи=1) нужно иметь dкод =3.
108
2.2. Коды с проверкой на четность
Простейшими корректирующими кодами являются коды с одной проверкой на четность. Здесь каждая разрешенная комбинация кода содержит четное число единиц, число проверочных символов r=1, и значение этого проверочного символа определяется линейной комбинацией информационных символов
an ak 1 a1 a2 .... ak . |
(7.4) |
Знак есть символ операции суммирования по mod2.
Код с проверкой на четность – это линейный блочный код, и его можно задать производящей матрицей, чаще всего в канонической форме. Например, для кода (3,2) матрица имеет вид
G |
Ik R |
1 0 1 , |
(7.5) |
|
|
0 11 |
|
где Ik – единичная матрица (k |
k). |
|
|
В этом случае кодовая комбинация v может быть построена |
|||
по общему для линейных блочных кодов правилу |
|
||
|
v=aG. |
(7.6) |
|
Здесь необходимо |
выполнить взвешенное |
суммирование |
|
строк производящей матрицы в соответствии с весовыми коэффициентами, равными элементам информационной КК. Однако при таком способе кодирующее устройство оказывается сложнее, чем при кодировании по уравнению (7.4). Поэтому для кода в параллельной форме используют в качестве кодера k- входовый сумматор по mod 2, а для кода в последовательной форме проще для формирования проверочного разряда использовать одну ячейку двоичного триггерного счетчика.
Схема кодера для кода (7,6), используемого в данной работе, приведена на рис. 7.1. К шести информационным символам, поступающим на вход кодера, добавляется один проверочный символ так, чтобы сумма единиц в каждой КК стала четной. Подсчет числа единиц в поступающей последовательности ин-
формационных символов a1 ,..., a6 производится при подаче
шести тактовых импульсов (ТИ) в одноразрядном двоичном счетчике (триггере) Т. Этот триггер оказывается в единичном
109
состоянии, если число единиц нечетно, и в нулевом состоянии в противном случае. Тогда в качестве проверочного символа a7 просто передается состояние счетного триггера.
Декодирование кодов с проверкой на четность основано на проверке соотношения
c a1 a2 .... an 0, |
(7.7) |
где ai - принятые символы.
a6,…,a1 |
T |
|
ТИ |
a7,…,a1 |
|
|
|
|
|
ТИ |
||
|
|
|
|
||||||
a7 |
T |
|
|
|
с |
||||
|
|
|
|
|
|
||||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
Рис. 7.1. Схема кодера |
Рис. 7.2. Схема декодера |
кода с проверкой |
кода с проверкой |
на четность (7,6) |
на четность (7,6) |
В процессе декодирования принятой КК при помощи аналогичного счетного триггера производится проверка на четность числа единиц в КК. Если к концу КК триггер оказывается в единичном состоянии (число единиц в принятом слове нечетно), это свидетельствует о наличии ошибки нечетной кратности. Схема декодера приведена на рис. 7.2.
2.3. Кодирование циклическим кодом
Впоисках более простой техники кодирования и декодирования были созданы так называемые циклические коды.
Циклические коды относят к классу линейных блочных. Основное свойство циклических кодов состоит в том, что циклическая перестановка в КК дает разрешенную КК, т.е. КК, принадлежащую данному коду. Циклической называют такую перестановку, при которой все символы смещаются в ту или иную сторону, при этом последний символ переходит на место первого или наоборот.
Втеории циклических кодов КК представляют в виде полиномов переменной x
V (x) a0 x |
0 |
1 |
... an 1x |
n 1 |
, |
(7.8) |
|
a1x |
|
|
110
где ai - коэффициенты полинома, принимающие значения (0,1). Например, КК двоичного кода можно записать в виде полинома следующим образом
0111 x x2 x3. |
(7.9) |
При таком представлении циклическая перестановка вправо есть результат простого умножения данного полинома на х. Чтобы произведение не содержало степеней больше, чем (n–1), будем полагать формально xn=1, то есть xn–1=xn+1=0.
Умножение и деление полиномов выполняют по обычным правилам алгебры, только при делении вычитание заменяют сложением по mod 2. Действительно, из равенства 1 1=0 следует, что 1=–1, т.е. операции сложения и вычитания совпадают. Кроме того, следует учитывать, что
xm xm xm (1 1) 0. |
(7.10) |
Циклический кoд однозначно задается с помощью так называемого производящего полинома степени r
r |
. |
(7.11) |
g(x) g0 g1x ... ar x |
|
Таблицу полиномов для циклических кодов с кодовым расстоянием dкод=3 можно найти, например, в [1].
Таким образом, существуют три способа представления циклических кодов:
1) производящей матрицей G. В качестве строк производящей матрицы выбирает двоичные комбинации, соответствующие производящему полиному g(x) и (k–1) полиномам, полученным из него путем циклических сдвигов
|
g(x) |
|
|
G |
x g(x) |
; |
(7.12) |
|
|||
. . . |
|
||
|
|
|
xk 1 
g(x)
2) системой r линейных уравнений, позволяющих вычислить значения проверочных разрядов по информационным. Уравнения для вычисления могут быть получены на основе проверочной матрицы Н. В качестве первой строки матрицы Н выбирают комбинацию, соответствующую проверочному полино-