Лекция 26
КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ЦИКЛИЧЕСКИХ КОДОВ
26.1. Принципы построения кодирующих и декодирующих
устройств циклических кодов
26.2. Вероятности ошибочного декодирования циклических кодов
26.1. Принципы построения кодирующих и декодирующих
устройств циклических кодов
Основными элементами циклического кодера являются: регистр сдвига, сумматоры по модулю 2 и коммутатор. Регистр сдвига
является динамическим запоминающим устройством (рис 26.1), в котором хранятся двоичные символы 0 или 1.
Рис. 26.1. Регистр сдвига
Сумматор по модулю 2 осуществляет сложение поступающих на его входы символов 0 и 1.
Изображение схем может быть таким, как показано на рис. 26.2.
Коммутатор осуществляет последовательное считывание поступающих на его входы (контакты) символов и устанавливает на
выходе очередность посылки кодовых символов в канал связи. Встречаются 3 варианта изображений коммутаторов в схемах
кодеров (рис. 26.3)
На рис. 26.3, а представлена кольцевая схема коммутатора, на рис. 26.3, б – линейная, на рис. 26.3, в – в виде регистра
сдвига.
Кодирующие и декодирующие устройства циклических кодов строятся на основе регистров с обратными связями. Такие
регистры иногда называют многотактными линейными переключающими схемами. При кодировании и декодировании
циклических кодов получаемый остаток содержит число разрядов, равное показателю степени порождающего многочлена
)
(
x
g
. Поэтому регистр с обратными связями (ОС) должен содержать
k
ячеек памяти. Как ранее указывалось, столбцы
проверочной матрицы
H
являются остатками от деления одночлена
i
x
на
)
(
x
g
. Разделить же
i
x
при помощи регистра с
ОС это значит осуществить сдвиг записанной в этот регистр „1" на
i
тактов после ввода ее в первую ячейку. Таким образом,
при каждом сдвиге записанной в регистр „1” должен получаться остаток, соответствующий делению
i
x
на
)
(
x
g
.
Следовательно, содержание регистра при каждом тактовом сдвиге должно соответствовать содержанию столбца проверочной
матрицы.
В качестве примера на рис.26.4 показаны схема регистра с ОС для порождающего многочлена
1
)
(
3
+
+
=
x
x
x
g
и
состояние ячеек этого регистра при сдвиге «1» записанных в первую ячейку (табл. 26.1). На конкретном примере покажем, что
данный регистр производит операцию деления.
Пусть требуется закодировать кодовую комбинацию вида
1 1 1 1,
многочлен которой имеет вид
1
)
(
2
3
+
+
+
=
x
x
x
x
G
.
Разделим многочлен
(
)
3
2
3
1
)
(
x
x
x
x
x
x
G
k
+
+
+
=
и отметим остатки, полученные перед каждым следующим тактом деления:
остаток перед 2-м тактом деления
остаток перед 3-м тактом деления:
остаток
Рис. 26.4. Схема регистра с ОС для порождающего многочлена
1
)
(
3
+
+
=
x
x
x
g
.
Табл. 26.1 К пояснению процесса кодирования
Деление сводится к последовательному сложению по модулю 2 делителя со старшими разрядами делимого или полученного
остатка. Регистр с обратными связями производит аналогичные операции. Определим содержание регистра перед каждым
тактом деления и сравним их с остатками, полученными путем обычного деяния.
Процесс деления в регистре производится только при поступлении "1" в цепь обратной связи. Поэтому содержание регистра при
котором "1" находится в последней ячейке, будет являться остатком перед следующим тактом деления. В табл. 26.1 показано
содержание ячеек регистра по тактам. Сравнение остатков, полученных как при обычном делении, так и при делении с
помощью регистра, показывает, что они полностью совпадают.
Регистры с обратными связями в соответствии с выбранным порождающим многочленом строятся по следующим правилам:
1. Число ячеек регистра выбирают равным степени порождающего многочлена
()
k
.
2. Количество сумматоров по модулю 2 берется на единицу меньше числа ненулевых членов порождающего многочлена.
3. Входы всех ячеек регистра обозначают
. Выход последней ячейки обозначается
, а вход первой -
.
Рис 26.5 Схема регистра с ОС для порождающего многочлена
1
)
(
3
+
+
=
x
x
x
g
с обозначением
k
x
.
4. Сумматоры по модулю 2 устанавливаются на входе тех ячеек, для которых в формуле порождающего многочлена
i
x
имеет
ненулевое значение. Например, для
1
)
(
3
+
+
=
x
x
x
g
(см.рис.26.4) сумматоры устанавливаются на входах ячеек 1 и 2
триггеров.
5. Выход последней ячейки соединяется с одним из входов сумматоров.
6. Выходы предыдущих ячеек соединяются со входами последующих через сумматоры или без них, в зависимости от того,
установлены они между ячейками или нет.
Структурная схема кодирующего устройства при порождающем многочлене
1
)
(
4
+
+
=
x
x
x
g
показана на рис.26.6. В
регистре с обратными связями передаваемая кодовая комбинация делится на исходный многочлен. При помощи линии
задержки передаваемая комбинация смещается на
k
разрядов (в данном случае
4
k
=
), что равносильно умножению
многочлена, отображающего передаваемую кодовую комбинацию, на
k
x
.
Устройство функционирует следующим образом. Передаваемая кодовая комбинация последовательно подается на вход
регистра и линии задержки. Ключ
2
K
находится в положений «1» ключ
1
K
- в положении «Включено».
После того как последний импульс с выхода линии задержки передан в линию связи, ключ
2
K
. переключается в положение ,,
2"
1
K
- в положение „Выключено" и содержимое регистра (остаток от деления) передается в линию связи.
На приемной стороне при помощи подобного же устройства многочлен, отображающий принятую кодовую комбинацию, делится
на многочлен
)
(
x
g
Приведенная схема кодирующего устройства обладает одним существенным недостатком. Кодированное сообщение
задерживается на число тактов, равное числу ячеек регистра. Устранить такой недостаток можно при использовании
кодирующего.устройства без линии задержки. В качестве примера на рис.26.9 изображена структурная схема такого устройства
с
1
)
(
4
+
+
=
x
x
x
g
.
Регистры с обратными связями для таких кодирующих устройств строятся по правилам, указанным ранее. Однако один из
сумматоров устанавливается не на входе первой ячейки памяти, а на выходе последней ячейки.
Декодирующие устройства также строятся на основе использования регистров с обратными связями. На рис.26.10 приведена
структурная схема декодирующего устройства, предназначенного для обнаружения ошибок. После приема кодовой комбинации
в регистре с обратными связями образуется остаток
()
Rx
. Если этот остаток равен 0, то сигнал запрета на выдачу принятой
кодовой комбинации потребителю не выдается.
При использовании циклических кодов в качестве кодов с исправлением ошибок схема декодирующего устройства
усложняется.
Кратко рассмотрим методику построения таких декодирующих устройств для наиболее простого метода исправления ошибок
-последовательного.
Этот метод основан на следующем свойстве. Если возникшая в кодовой комбинации ошибка исправляема, то после введения
принятой кодовой комбинации в регистр с ОС можно восстановить вектор ошибок. После поразрядного сложения этого вектора с
вектором, отображающим принятую кодовую комбинацию, ошибка исправляется. Структурная схема такого декодирующего
устройства приведена на рис.26.11.
Принятая кодовая комбинация поразрядно поступает в регистр со сдвигом и в регистр с ОС. Затем принятая комбинация
последовательным кодом через сумматор по модулю 2 (М2) выдается потребителю. В то время, когда искаженный разряд будет
на выходе регистра со сдвигом, при исправляемых кодом ошибках содержание регистра с ОС будет вполне определенным.
Селектор выделяет эту известную кодовую комбинацию и выдает на сумматор по модулю 2 импульс для исправления
искаженного разряда. Одновременно в регистр с ОС записывается кодовая комбинация, при помощи которой устраняется
влияние исправленного разряда на содержание этого регистра. Так, например, при
1
)
(
3
+
+
=
x
x
x
g
длине кодовой
комбинации
6
n
=
селектор должен выделять комбинацию 111, а в регистр с ОС вводиться комбинация 101.
Рис 26.11 Декодирующее устройство с исправлением ошибок
26.2. Вероятности ошибочного декодирования циклических кодов
Вектором ошибки называется двоичная последовательность длины
n
, в которой единицы стоят на позициях символов
принятых с ошибкой. Отсюда вероятность не обнаружения ошибки заданным кодом равна вероятности появления в заданном
дискретном канале векторов ошибок, совпадающих с кодовыми словами
Относительно просто эти вероятности могут быть рассчитаны для двоичнго симметричного канала без памяти. В таком канале
каждый двоичный символ с некоторой фиксированной вероятностью
(
)
o
P
-
1
принимается правильно и с вероятностью
o
P
изменяется помехой на обратный. Передача/прием каждого символа полагается событием независимым (канал без памяти).
Если по такому каналу передается кодовое слово длины
n
,
то вероятность
)
0
(
n
P
того, что не произойдет ни одной ошибки,
равна
(
)
n
o
P
-
1
.
Вероятность
)
1
(
n
P
того, что будет одна ошибка в заданном символе, равна
(
)
1
1
-
-
n
o
o
P
P
.
Вероятность того, что слово на выходе канала будет отличаться от переданного слова в заданных
i
разрядах, т.е. вектор
ошибок содержит
i
единиц, равна
(
)
i
n
o
i
P
P
P
-
-
=
1
0
*
.
Вероятность того, что слово на выходе канала будет отличаться от переданного слова в любых
i
разрядах, равна
(
)
i
n
o
i
i
n
n
P
P
C
i
P
-
-
=
1
)
(
0
,
где
i
n
C
—
число сочетаний из
n
по
i
.
Предположим, что некоторый линейный код (5,3) содержит одно нулевое слово (как всякий линейный код), два слова, вес
которых равен 2, четыре слова — весом 3, одно слово — весом 4 (всего
8
2
2
5
=
=
m
слов).
Вероятность необнаруживаемой этим кодом ошибки равна вероятности появления в ДСК векторов ошибок, совпадающих с
кодовыми словами, т.е.:
(
)
).
1
(
)
1
(
4
1
2
)
4
(
)
3
(
4
)
2
(
2
)
(
4
2
3
3
2
5
5
5
o
o
o
o
o
o
HO
P
P
P
P
P
P
P
P
P
i
P
-
+
-
+
-
=
=
+
+
=
В режиме исправления ошибок декодер вычисляет остаток
)
(
x
R
от деления принятой последовательности
)
(
'
x
F
на
)
(
x
g
.
Этот остаток называют
синдромом.
Принятый полином
)
(
'
x
F
представляет собой сумму по модулю 2 переданного слова
)
(
x
F
и вектора ошибок
)
(
x
E
:
)
(
)
(
)
(
'
x
E
x
F
x
F
Е
=
.
Тогда синдром
)
(
mod
)
(
'
)
(
x
g
x
F
x
S
=
,
так как по определению циклического кода
0
)
(
mod
)
(
=
x
g
x
F
. Некоторому
синдрому
)
(
x
S
может быть поставлен в соответствие определенный вектор ошибок
)
(
x
E
.
Тогда переданное слово
)
(
x
F
находят, складывая
)
(
)
(
'
)
(
x
E
x
F
x
F
Е
=
.
Однако один и тот же синдром может соответствовать
m
2
различным векторам ошибок. Предположим, синдром
)
(
1
x
S
соответствует вектору ошибок
)
(
1
x
E
. Но и все векторы ошибок, равные сумме
)
(
)
(
1
x
E
x
F
Е
, где
)
(
x
F
- любое кодовое
слово, будут давать тот же синдром. Поэтому, поставив в соответствие синдрому
)
(
1
x
S
вектор ошибок
)
(
1
x
E
,
мы будем
осуществлять правильное декодирование в случае, когда действительно вектор ошибок равен
)
(
1
x
E
, во всех остальных
)
1
2
(
-
m
случаях декодирование будет ошибочным.
Для уменьшения вероятности ошибки декодирования из всех возможных векторов ошибок, дающих один и тот же синдром,
следует выбирать в качестве исправляемого наиболее вероятный в заданном канале.
Например, для для двоичнго симметричного канала, в котором вероятность
o
P
ошибочного приема двоичного символа
существенно меньше вероятности
(
)
o
P
-
1
правильного приема, вероятность появления векторов ошибок уменьшается с
увеличением их веса
i
. В этом случае следует исправлять в первую очередь вектор ошибок меньшего веса.
Если кодом могут быть исправлены только все векторы ошибок веса
i
и меньше, то любой вектор ошибки веса от
1
+
i
до
п
будет приводить к ошибочному декодированию.
Вероятность ошибочного декодирования будет равна вероятности
появления векторов ошибок веса
и больше в
заданном канале. Для ДСК эта вероятность будет равна
(
)
е
+
=
-
-
=
>
n
i
j
j
n
o
j
j
n
n
P
P
C
i
P
1
0
1
)
(
Общее число различных векторов ошибок, которые может исправлять циклический код, равно числу ненулевых синдромов
1
2
-
-
m
n
.
