Кодовая комбинация циклического кода содержит ошибку если

Схема
циклического кода

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

1. Кодирующее
   устройство строится в соответствии с
   видом образующего полинома и в основе
   своей представляет собой регистр сдвига
   с обратными связями через сумматоры
   по модулю два.

2. Количество ячеек
   памяти в регистре равно степени
   образующего полинома.

3. Количество
   сумматоров по модулю два равно весу
   образующего полинома минус единица.

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

Структурная схема
кодирующего устройства для кода (9,5) и
образующего полинома P(x)=
x⁴
+ x
+ 1, построенная в соответствии с
вышесказанным, приведена на рисунке.

В представленной
схеме кодера имеется 4 триггера: m1,
m2,
m3
и m4,
в качестве ячеек памяти, 2 сумматора по
модулю два: C1 и C2, два ключа, представленных
в виде схем И1 и И2, и элемент ИЛИ. Схема
тактируемая.

Схема кодера
работает следующим образом.

Безизбыточный код
поступает на сумматор C2, после чего
происходит деление на образующий
полином, что реализуется с помощью
обратных связей через схему И1. Пока
поступает информационная кодовая
комбинация G(x), то есть в нашем примере
— с 1го по 5й такты, схема И1 открыта, а
схема И2 закрыта вследствие чего
информационные элементы поступают на
выход кодера. После k тактов, где k —
количество информационных разрядов,
ключ И1 размыкается, а ключ И2 замыкается
и с регистра сдвига на выход кодера
считывается остаток от деления R(x). В
последующие такты с 6го по 9й через схему
И2 остаток от деления выводится в линию
связи. Состояние триггеров на каждом
такте работы схемы представлено в
таблице.

Подробнее описание
работы устройства кодирования приведено
в приложении.

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

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

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

F
*(X) =
F(X)
+
E(X),

где
E
(X)
— многочлен ошибок.

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

Если же в результате
деления полинома F*(X)
на порождающий многочлен Р(х) остаток
R^’(х)
отличен от нуля, то это означает что
принятая кодовая комбинация содержит
ошибки.

Вид ненулевого
остатка R’(x),
называемого синдромом ошибки S(х), имеет
однозначное соответствие с ошибочным
разрядом и видом полинома однократной
ошибки Е(х) для всех кодовых комбинаций
циклического кода. Например, для
циклического кода (9,5) при заданном
образующем полиноме P(x)=
x⁴
+ x
+ 1 остаток R’(x)
всегда будет иметь вид S(х)=0011, если
ошибка происходит в пятом разряде
входной кодовой комбинации, независимо
от вида переданной кодовой комбинации
F(х).

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

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

Для исправления
однократной ошибки в принятой кодовой
комбинации F*(X)
необходимо определить место ошибки. С
этой целью производится деление принятого
полинома на порождающий многочлен Р(х).
Для примера рассмотрим код (9,5). Если на
9-ом такте в декодере будет зафиксирована
хотя бы одна единица, то деление происходит
до тех пор, пока в делителе не будет
зафиксирована так называемая “особая”
кодовая комбинация Т. Вид этой комбинации
зависит только от вида порождающего
многочлена Р(х) и длины n комбинации
циклического кода F(х), причем находится
Т как остаток от деления хⁿ
на P(x).
В нашем примере, для кода (9,5) и порождающего
многочлена Р(х)=х⁴+х+1
“особая” кодовая комбинация, всегда
имеет вид 1010.

Номер такта, на
котором в делителе возникает “особая”
кодовая комбинация, указывает место
ошибочного разряда в принятой кодовой
комбинации. При считывании этой комбинации
из буферного регистра ошибочный разряд
исправляется (инвертируется).

Циклический код
(9,5) гарантированно исправляет только
однократные ошибки. Ошибки более высокой
кратности код (9,5) не исправляет.

Рассмотрим
пример декодирования циклического кода
P(x)=x³+x+1.

Вначале
строится структурная схема декодера.
Для кода P(x)=x³+x+1
она выглядит следующим образом:

Структурная
схема декодера строится по тем же
принципам, что и схема кодера. В состав
декодера циклического кода (7,4) входят:
буферный регистр на 7 разрядов, декодирующий
регистр (регистр-делитель), схема ИЛИ–НЕ,
схема И, а также – управляющее устройство,
замыкающее ключ К1 после 7-го такта (на
схеме устройство не показано). На вход
декодирующего регистра поступает
кодовая комбинация, которая делится на
порождающий полином в декодирующем
регистре. По окончании деления, после
7 тактов, в триггерах m1m3
декодирующего регистра записывается
остаток от деления. Если при этом хотя
бы один из триггеров m1m3
находится в единичном состоянии, то это
означает, что в принятой кодовой
комбинации имеется ошибка. Для обнаружения
места ошибки деление происходит далее
и на каждом такте разряды с выходов
триггеров m1m3
поступают на вход схемы ИЛИ–НЕ. На
выходе этой схемы формируется нулевой
разряд, который при замкнутом ключе К1
поступает на второй вход схемы И. На
первый вход схемы И поступает кодовая
комбинация из буферного регистра. Под
действием нулевого разряда с выхода
схемы ИЛИ-НЕ схема И запирается и кодовая
комбинация не поступает из буферного
регистра на выход схемы декодера.

Если
все триггеры m1m3
декодирующего регистра имеют значение
«0» после 7-го такта, то дальнейшее деление
не происходит. Тогда схема И пропускает
на выход декодера безошибочно принятую
кодовую комбинацию из буферного
регистра, причем потребителю направляются
первые четыре разряда, составляющих
информационную кодовую комбинацию
G(х).

На
основании построенной схемы декодера
строится таблица состояния триггеров
или как ее еще называют таблица
декодирования. Слева записывается
комбинация, которую требуется проверить
F*(X),
она может быть как верной, так и ошибочной,
поэтому записываю ее со звездочкой. При
этом, С=m_3пр,
m₁=C+a,
m₂=C+m_1пр,
m₃=m_2пр
(определяется из схемы декодера) Если
при декодировании m₃=0,
m₂=0,
m₁=0
(старшим считается разряд m₃),
то ошибок в принятой комбинации нет.
Если при декодировании обнаружен
синдром, то происходит дальнейшее
декодирование для определения разряда,
в котором есть ошибка, путем поиска
особой комбинации (посчитать особую
комбинацию 001). Номер такта, при котором
обнаружена такая комбинация будет
разрядом, в котором есть ошибка.

Пример
1.

Дано:
P(x)=x³+x+1.
На приемник приходит комбинация 1101001.

Задача:
проверить, верна ли комбинация, если
нет, исправить.

a	m1	m2	m3	c
0	0	0
1	1	0	0	0
1	1	1	0	0
0	0	1	1	0
1	0	1	1	1
0	1	1	1	1
0	1	0	1	1
1	0	0	0	1

Ответ:
Кодовая комбинация передана без ошибок.

Пример
2.

Дано:
P(x)=x³+x+1.
На приемник приходит комбинация 1110011.

Задача:
проверить, верна ли комбинация, если
нет, исправить.

a	m1	m2	m3	c
0	0	0
1	1	0	0	0
1	1	1	0	0
1	1	1	1	0
0	1	0	1	1
0	1	0	0	1
1	1	1	0	0
1	1	1	1	0
0	1	0	1	1
0	1	0	0	1

Ответ:
Ошибка во втором разряде. Верная кодовая
комбинация 1010011

Рассмотрим
еще один пример декодирования циклических
кодов. Он
заключается в следующем. Принятую
кодовую комбинацию делят на P(X),
и если остаток R(X)=0,
то комбинация принята без искажений.
Наличие ос­татка свидетельствует о
том, что комбинация принята искаженной.
Рассмотрим дальнейшую процедуру
исправления.

1. Если
   вес остатка равен или меньше количества
   исправляемых ошибок, т.е.
   w<s,
   то принятую комбинацию суммируют по
   модулю 2 с остатком, в результате чего
   образуется исправленная комбинация;

2. Если
   вес остатка больше количества исправляемых
   ошибок, т.е.
   w
   > s,
   то производят циклический сдвиг
   комбинации на один разряд влево и
   образованную в результате сдвига
   комбинацию снова де­лят на P(X).
   Если вес остатка, образованного при
   делении меньше ли равен количеству
   исправляемых ошибок, то циклически
   сдвинутую комбинацию суммируют по
   модулю два с остатком и затем циклически
   сдвигают ее в обрат­ную сторону, т.е.
   вправо на один разряд. В результате
   чего имеем исправленную комбинацию;

3)
Если
после циклического сдвига на один разряд
вес остатка по-прежнему
больше
количества исправляемых ошибок,
производят дальнейшие цик­лические
сдвиги влево. При этом после каждого
сдвига образованную комбина­цию делят
на P(X)
и проверяют вес остатка. При
w
< s
реализуют действия, указанные в пункте
2, с той лишь разницей, что обратных
циклических сдви­гов вправо производят
столько, сколько сдвигов производили
влево.

Пример
2.14.
Пусть исходная комбинация
G(X)
= 1001, закодированная с помощью P(X)
= 1011 и
s=1,
имеет вид
F(X)
= 1001110. При передаче происходит ошибка
и в приемник комбинация поступает в
виде
F
*(X)
= 1101110. Проверить наличие ошибки и, если
она существует, исправить ее.

Задача.
В приемник поступает комбинация 1101110.
Образующий полином задан в виде двоичной
комбинации 1011. Количество исправляемых
ошибок S=1.
Проверить наличие ошибки и, если она
существует, исправить ее. Для проверки
использовать оба метода.

Делим
комбинацию 1101110 на 1011 и находим, что
остаток
R(
X)
= 111. Так как
w
= 3 >
s
= 1, то сдвигаем комбинацию 1101110 циклически
на один разряд влево — 1011101. В результате
деления этой комбинации на P(X)
находим остаток R(X)
= 101. Вес этого остатка
w
= 2 >
s
= 1. Осуществляем новый циклический сдвиг
влево — 0111011. Деление на P(X)
дает остаток R(X)=001,
вес которого равен
s.
Суммируем: 0111011+001 =0111010. Теперь производим
два циклических сдвига по­следней
комбинации вправо: после первого она
принимает вид 0011101, после второго 1001110,
т.е. в результате есть исправленная
комбинация. Проверка по­казывает, что
эта комбинация делится на P(X)
без остатка.

1

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

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

В
общей структурной схеме СПДС задачу защиты от ошибок выполняет кодер и
декодер канала, который иногда называют УЗО.

5.1
Понятие о корректирующих кодах

Пусть
имеется источник сообщений с объемом алфавита К.

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

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

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

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

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

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

Перебрав
все возможные пары разрешенных комбинаций рассматриваемого кода можно
найти минимальное расстояние Хемминга d₀.

Минимальное
расстояние d₀ — называется кодовым расстоянием

Кодовое
расстояние определяет способность кода обнаруживать и исправлять ошибки.

У
простого кода d₀=1 – он не обнаруживает и не исправляет ошибки.
Так как любая ошибка переводит одну разрешенную комбинацию в другую.

В
общем случае справедливы следующие соотношения

– для обнаруживающей способности

– для исправляющей способности

Линейные
коды.

Двоичный
блочный код является линейным если сумма по модулю 2 двух кодовых слов
является также кодовым словом.

Линейные
коды также называют групповыми.

Введем
понятия группы.

Множество
элементов с определенной на нем групповой операцией называется группой,
если выполняется следующие условия:

1.
Замкнутость g_ig
_j= g_k G
в результате операции с двумя элементами группы получается третий, так
же принадлежащий этой группе.
2. Ассоциативность
(сочетательность) (g_ig_j)

g_k = g_i
(g_j g_k)
3. Наличие нейтрального
элемента g_j
e = g_j
4. Наличие
обратного элемента. g_i
(g_i)^-1= e

Если
выполняется условие g_i
g_j = g_j
g_i, то группа называется коммутативной.

Множество
кодовых комбинаций n-элементного кода является замкнутой группой с заданной
групповой операцией сложение по модулю 2.

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

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

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

5.2
ЦИКЛИЧЕСКИЕ КОДЫ

Широкое
распространение на практике получил класс линейных кодов, которые называются
циклическими. Данное название происходит от основного свойства этих кодов:

если
некоторая кодовая комбинация принадлежит циклическому коду, то комбинация
полученная циклической перестановкой исходной комбинации (циклическим
сдвигом), также принадлежит данному коду.

.

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

Синдромом
ошибки в этих кодах является наличие остатка от деления принятой кодовой
комбинации на производящий полином.

Эти
свойства используются при построении кодов, кодирующих и декодирующих
устройств, а также при обнаружении и исправлении ошибок.

Представление
кодовой комбинации в виде многочлена.

Описание
циклических кодов и их построение удобно проводить с помощью многочленов
(или полиномов).

В
теории циклических кодов кодовые комбинации обычно представляются в виде
полинома. Так, n-элементную кодовую комбинацию можно описать полиномом
(n-1) степени, в виде

.

где
={0,1},
причем =
0 соответствуют нулевым элементам комбинации, а =
1 — ненулевым.

Запишем
полиномы для конкретных 4-элементных комбинаций

Действия
над многочленами.

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

,

поскольку
.

Следует
отметить, что действия над коэффициентами полинома (сложение и умножение)
производятся по модулю 2.

Рассмотрим
операцию деления на следующем примере:

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

Отметим,
что запись кодовой комбинации в виде многочлена, не всегда определяет
длину кодовой комбинации. Например, при n = 5, многочлену
соответствует кодовая комбинация 00011.

Алгоритм
получения разрешенной кодовой комбинации циклического кода из комбинации
простого кода

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

Требуется
определить разрешенную кодовую комбинацию циклического кода (n, k).

1. Умножаем многочлен
   исходной кодовой комбинации на



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



3. Окончательно разрешенная
   кодовая комбинация циклического кода определится так

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

Формирование
базиса (производящей матрицы) циклического кода

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

Вариант первый.

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

Полученная
матрица и будет базисом циклического кода. Причем, в данном случае, разрешенные
комбинации заведомо разделимы (т.е. информационные и проверочные элементы
однозначно определены).

Вариант второй.

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

В
данном случае код будет неразделимым.

Получив
базис ЦК, можно получить все разрешенные комбинации, проводя сложение
по модулю 2 кодовых комбинаций базиса в различных сочетаниях и плюс НУЛЕВАЯ.

Циклические
коды достаточно просты в реализации, обладают высокой корректирующей способностью
(способностью исправлять и обнаруживать ошибки) и поэтому рекомендованы
МСЭ-Т для применения в аппаратуре ПД. Согласно рекомендации V.41 в системах
ПД с ОС рекомендуется применять код с производящим полиномом

Построение
кодера циклического кода

Рассмотрим
код (9,5) образованный полиномом

.

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

1. Умножение полинома
   на одночлен

эквивалентно добавлению
к двоичной последовательности соответствующей G(x) , r — нулей справа.

Пусть

тогда

Для
реализации операции добавления нулей используется r-разрядный регистр
задержки.

1. Рассмотрим более
   подробно операцию деления:

Как
видим из примера, процедура деления одного двоичного числа на другое сводится
к последовательному сложению по mod2 делителя [10011] с
соответствующими членами делимого [10101], затем с двоичным числом, полученным
в результате первого сложения, далее с результатом второго сложения и
т.д., пока число членов результирующего двоичного числа не станет меньше
числа членов делителя.

Это
двоичное число и будет остатком .

Построение
формирователя остатка циклического кода

Структура
устройства осуществляющего деление на полином полностью определяется видом
этого полинома. Существуют правила позволяющие провести построение однозначно.

Сформулируем
правила построения ФПГ.

1. Число ячеек памяти
   равно степени образующего полинома r.
2. Число сумматоров
   на единицу меньше веса кодирующей комбинации образующего полинома.
3. Место установки
   сумматоров определяется видом образующего полинома.

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

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

Структурная
схема кодера циклического кода (9,5)

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

Рассмотрим
работу этой схемы

1.
На первом этапе К₁– замкнут К₂ – разомкнут. Идет
одновременное заполнение регистров задержки и сдвига информ. элементами
(старший вперед!) и через 4 такта старший разряд в ячейке №4

2.
Во время пятого такта К₂ – замыкается а К₁ – размыкается
с этого момента в ФПГ формируется остаток. Одновременно из РЗ на выход
выталкивается задержание информационные разряды.

За
5 тактов (с 5 по 9 включительно) в линию уйдут все 5-информационных элемента.
К этому времени в ФПГ сформируется остаток

3.
К₂ – размыкается, К₁ – замыкается и в след за информационными
в линию уйдут элементы проверочной группы.

4.
Одновременно идет заполнение регистров новой комбинацией.

Второй
вариант построения кодера ЦК.

Рассмотренный
выше кодер очень наглядно отражает процесс деления двоичных чисел. Однако
можно построить кодер содержащий меньшее число элементов т.е. более экономичный.

Устройство
деления на производящий полином
можно реализовать в следующем виде:

За
пять тактов в ячейках будет сформирован такой же остаток от деления, что
и в рассмотренном выше Формирователе проверочной группы. (ФПГ).

За
эти же 5 тактов информационные разряды, выданные сразу на модулятор.

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

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

Окончательно
структурная схема экономичного кодера выглядит так.

—
На первом такте Кл.1 и Кл.3 замкнуты, информационные элементы проходят
на выход кодера и одновременно формируются проверочные элементы.

—
После того, как в линию уйдет пятый информационный элемент, в устройстве
деления сформируются проверочные;

—
на шестом такте ключи 1 и 3 размыкаются (разрываются обратная связь),
а ключ 2 замыкается и в линию уходят проверочные разряды.

Ячейки
при этом заполняются нулями и схема возвращается в исходное состояние.

Определение
ошибочного разряда в ЦК.

Пусть
А(х)-многочлен соответствующий переданной кодовой комбинации.

Н(х)-
многочлен соответствующей принятой кодовой комбинацией.

Тогда
сложение данных многочленов по модулю два даст многочлен ошибки.

E(x)=A(x)

H(x)

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

Остаток
– полученный от деления принятого многочлена H(x) на производящей P_r(x)
равен остатку полученному при делении соответствующего многочлена ошибок
E(x) на P_r(x)

При
этом ошибке в каждом разряде будет соответствовать свой остаток R(x) (он
же синдром), а значит, получив синдром можно однозначно определить место
ошибочного разряда.

Алгоритм
определения ошибки.

Пусть
имеем n-элементные комбинации (n = k + r) тогда:

1.
Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде
[1000000000], на образующей поленом P_r(x)

2.
Делим полученный полином Н(х) на P_r(x) и получаем текущий остаток
R(x).

3.
Сравниваем R₀(x) и R(x).

—
Если они равны, то ошибка произошла в старшем разряде.

—
Если «нет», то увеличиваем степень принятого полинома на Х и снова проводим
деления

в)
Опять сравниваем полученный остаток с R₀(x)

—
Если они равны, то ошибки во втором разряде.

—
Если нет, то умножаем Н(х)х² и повторяем эти операции до тех
пор, пока R(X) не будет равен R₀(x).

Ошибка
будет в разряде соответствующем числу на которое повышена степень Н(х)
плюс один.

Например:

то номер ошибочного разряда 3+1=4

Пример
декодирования комбинации ЦК.

Положим,
получена комбинация H(х)=111011010

Проанализируем
её в соответствии с вышеприведенным алгоритмом.

Реализуя
алгоритм определения ошибок, определим остаток от деления вектора соответствующего
ошибке в старшем разряде Х⁸ на производяший полином P(x)=X⁴+X+1

X⁸
X²+X+1

X⁸+X⁵+X⁴
x⁴+x+1

X⁵+X⁴

X⁵+X²+X

X⁴+X²+X

X⁴+X+1

X²+1=R₀(X)=0101

Разделим
принятую комбинацию на образующий полином

Полученный
на 9-м такте остаток, как видим, не равен R₀(X). Значит необходимо
умножить принятую комбинацию на Х и повторить деление. Однако результаты
деления с 5 по 9 такты включительно будут такими же, значит необходимо
продолжить деление после девятого такта до тех пор, пока в остатке не
будет R₀(Х). В нашем случае это произойдет на 10 такте, при
повышении степени на 1. Значит ошибки во втором разряде.

Декодер
циклического кода с исправлением ошибки

Если ошибка в первом
разряде, то остаток R₀(X)=10101 появления после девятого такта
в ячейках ФПГ.

Если
во втором по старшинству то после 10^го;
в третьем по
старшинству то после 11^го;
в четвертом
по старшинству то после 12^го
в пятом по старшинству
то после 13^го
в шестом по старшинству
то после 14^го
в седьмом по старшинству
то после 15^го
в восьмом по старшинству
то после 16^го
в девятом по старшинству
то после 17^го.

На
10 такте старший разряд покидает регистр задержки и проходит через сумматор
по модулю 2.

Если
и этому моменту остаток в ФПГ=R₀(X), то логическая 1 с выхода
дешифратора поступит на второй вход сумматора и старший разряд инвертируется.

В
нашем случае инвертируется второй разряд на 11 такте.

5.3
Выбор образующего полинома

Рассмотрим
вопрос выбора образующего полинома, который определяет корректирующие
свойства циклического кода. В теории циклических кодов показано, что образующий
полином представляет собой произведение так называемых минимальных многочленов
m_i(x), являющихся простыми сомножителями (то есть делящимся
без остатка лишь на себя и на 1) бинома xⁿ+ 1:

P(x)=m₁(x)*
m₃(x)…m_j(x), (*)

где
j = d₀ – 2 =( 2t_u.ош+1)
– 2 = 2 t_и.ош – 1.

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

для
любых значений l и t_и.ош существует циклический
код длины n =2^l – 1, исправляющий все ошибки
кратности t_и.ош и менее, и содержащий не более
проверочных элементов.

Так
как ,
то
откуда . (**)

Очевидно,
что для уменьшения времени передачи кодовых комбинаций, r следует
выбирать как можно меньше. Пусть, например, длина кодовых комбинаций n
= 7, кратность исправляемых ошибок t_и.ош =1. Из
(**) получим r = 1 ^. log₂ ( 7+1 )=3.

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

Таблица
минимальных многочленов

J=2tи.ош -1	Вид минимальных многочленов для
1	2	3	4	5	6	7
1	x2+x+1	x3+x+1	x4+x+1	x5+x+1	x6+x+1	x7+x+1
3	—	—	x4+x3+ +x2+x+1	x5+x4+ +x3+x2+1	x6+x4+ +x2+x+1	x7+x3+ +x2+x+1
5	—	—	—	x5+x4+ +x2+x+1	x6+x5+ +x2+x+1	x7+x4+ +x3+x2+1
7	—	—	—	—	x6+x3+1	X7+x6+x5+ +x4+x2+x+1

Определяя
образующий полином, нужно из столбца для соответствующего соотношения

выписать все многочлены, начиная с верхней строки до нижней с номером
j=2t_и.ош–1 включительно. После этого следует
перемножить выбранные минимальные многочлены в соответствии с (*). В частности,
если r=3, t_и.ош=1, j=2*1-1=1, образующий
полином будет представлять собой единственный минимальный многочлен P(x)=
m₁(x) = x³+x+1 (первая строка, второй столбец
таблицы ). Соответственно образующее число равно 1011.

Контрольные
вопросы по теме:

1. Что такое разрешенные
   и запрещенные кодовые комбинации.
2. Что называется
   расстоянием Хемминга.
3. Дайте понятие кодового
   расстояния и как его определить.
4. Как связано кодовое
   расстояние с исправляющей и обнаруживающей способностью кода.
5. Какой код называется
   линейным.
6. Какое множество
   называется группой.
7. Назовите основные
   свойства циклических кодов.
8. Запишите полином
   
   в двоичном виде.
9. Запишите полином,
   соответствующий двоичной записи 100111.
10. Получите остаток
    от деления полинома
    на .
11. Как получают разрешенные
    комбинации при циклическом кодировании.
12. Нарисуйте кодер
    для циклического кода, порождаемого полиномом .
    Поясните принцип работы кодера.
13. По какому признаку
    обнаруживают ошибку в принятой кодовой комбинации.
14. Каков алгоритм
    определения ошибочного разряда в комбинации циклического кода.
15. Нарисуйте структурную
    схему декодера, обеспечивающего обнаружение ошибок для кода (7,4) при
    производящем полиноме .
    Поясните принцип его работы.
16. Нарисуйте структурную
    схему декодера, обеспечивающего исправление однократной ошибки для кода
    (7,4) при производящем полиноме .
    Поясните принцип его работы.
17. Как выбирается
    образующий (производящий) полином?

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

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

Возможность помехоустойчивого кодирования осуществляется на основании теоремы, сформулированной Шенноном, согласно ей:

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

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

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

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

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

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

Если осуществляется кодирование с обнаружением ошибок, то кодовое расстояние должно быть хотя бы на единицу больше чем кратность обнаруживаемых ошибок, т. е.

d₀? q_{о ош} + 1.

Если данное условие не выполняется, то одни из ошибок обнаруживаются, а другие нет.

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

d₀? 2q_{и ош} + 1.

Если данное условие не выполняется, то одни из ошибок исправляются, а другие нет.

Следует отметить, что если код способен исправить одну ошибку (q_{и ош} = 1), что соответствует кодовому расстоянию 3 (d₀ = 1?2+1 = 3), то обнаружить он может две ошибки, т. к.

q_{о ош} = d₀ – 1 = 2.

Декодирование помехоустойчивых кодов

Декодирование — это процесс перехода от вторичного отображения сообщения к первичному алфавиту.

Декодирование помехоустойчивых кодов может осуществляться тремя способами: сравнения, синдромным и мажоритарным.

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

Синдромный способ  основан на вычислении определенным образом контрольного числа — синдрома ошибки (С). Если синдром ошибки равен нулю, то кодовая комбинация принята верно, если синдром не равен нулю, то комбинация принята не верно. Данный способ может быть использован в кодах с исправлением ошибок, в этом случае синдром указывает не только на наличие ошибки в кодовой комбинации, но и на место положение этой ошибки в кодовой комбинации. Для двоичного кода знание местоположения ошибки достаточно для ее исправления. Это объясняется тем, что любой символ кодовой комбинации может принимать всего два значения и если символ ошибочный, то его необходимо инвертировать. Следовательно, синдрома ошибки достаточно для исправления ошибок, если d₀? 2q_{и ош} + 1.

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

Классификация корректирующих кодов

Классификация корректирующих кодов представлена схемой (рисунок 4)

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

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

Неразделимые — это коды, в кодовых комбинациях которых нельзя выделить проверочные разряды.

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

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

Код с постоянным весом

Данный код относится к классу блочных не разделимых кодов. В нем все разрешенные кодовые комбинации имеют одинаковый вес. Примером кода с постоянным весом является Международный телеграфный код МТК-3. В этом коде все разрешенные кодовые комбинации имеют вес равный трем, разрядность же комбинаций n=7. Таким образом, из 128 комбинаций (N₀ = 2⁷ = 128) разрешенными являются Nа = 35 (именно столько комбинаций из всех имеют W=3). При декодировании кодовых комбинаций осуществляется вычисление веса кодовой комбинации и если W?3, то выносится решение об ошибке. Например, из принятых комбинаций 0110010, 1010010, 1000111 ошибочной является третья, т. к. W=4. Данный код способен обнаруживать все ошибки нечетной кратности и часть ошибок четной кратности. Не обнаруживаются только ошибки смещения, при которых вес комбинации не изменяется, например, передавалась комбинация 1001001, а принята 1010001 (вес комбинации не изменился W=3). Код МТК-3 способен только обнаруживать ошибки и не способен их исправлять. При обнаружении ошибки кодовая комбинация не используется для дальнейшей обработки, а на передающую сторону отправляется запрос о повторной передаче данной комбинации. Поэтому данный код используется в системах передачи информации с обратной связью.

Код с четным числом единиц

Данный код относится к классу блочных, разделимых, систематических кодов. В нем все разрешенные кодовые комбинации имеют четное число единиц. Это достигается введением в кодовую комбинацию одного проверочного символа, который равен единице если количество единиц в информационной комбинации нечетное и нулю ? если четное. Например:

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

101101 = 1 + 0 + 1 + 1 + 0 + 1 = 0 — разрешенная комбинация

101111 = 1 + 0 + 1 + 1 + 1 + 1 = 1 — запрещенная комбинация.

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

Код Хэмминга

Код Хэмминга относится к классу блочных, разделимых, систематических кодов. Кодовое расстояние данного кода d₀=3 или d₀=4.

Блочные систематические коды характеризуются разрядностью кодовой комбинации n и количеством информационных разрядов в этой комбинации k остальные разряды являются проверочными (r):

r = n — k.

Данные коды обозначаются как (n,k).

Рассмотрим код Хэмминга (7,4). В данном коде каждая комбинация имеет 7 разрядов, из которых 4 являются информационными,

При кодировании формируется кодовая комбинация вида:

а₁ а₂ а₃ а₄ b₁ b₂ b

где а_i — информационные символы;

b_i — проверочные символы.

В данном коде проверочные элементы b_i находятся через линейные комбинации информационных символов a_i, причем, для каждого проверочного символа определяется свое правило. Для определения правил запишем таблицу синдромов кода (С) (таблица 3), в которой записываются все возможные синдромы, причем, синдромы имеющие в своем составе одну единицу соответствуют ошибкам в проверочных символах:

• синдром 100 соответствует ошибке в проверочном символе b₁;
• синдром 010 соответствует ошибке в проверочном символе b₂;
• синдром 001 соответствует ошибке в проверочном символе b₃.

Синдромы с числом единиц больше 2 соответствуют ошибкам в информационных символах. Синдромы для различных элементов кодовой комбинации а_i и b_i должны быть различными.

Таблица 3 — Синдромы кода Хэмминга (7;4)

Число	Элементы синдрома	Элементы кодовой
синдрома	С1	С2	С3	комбинации
1	0	0	1	b3
2	0	1	0	b2
3	0	1	1	a1
4	1	0	0	b1
5	1	0	1	a2
6	1	1	0	a3
7	1	1	1	a4

Определим правило формирования элемента b₃. Как следует из таблицы, ошибке в данном символе соответствует единица в младшем разряде синдрома С4. Поэтому, из таблицы, необходимо отобрать те элементы а_i у которых, при возникновении ошибки, появляется единица в младшем разряде. Наличие единиц в младшем разряде, кроме b₃,соответствует элементам a₁, a₂ и a₄. Просуммировав эти информационные элементы получим правило формирования проверочного символа:

b₃ = a₁ +    a₂  +  a₄

Аналогично определяем правила для b₂ и b₁:

b₂ = a₁ +  a₃ + a₄

b₁ = a₂ +  a₃ + a₄

Пример 3, необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем b_i:

b₁ = 1 +  0 + 1 = 0; b₂ = 1 + 0 + 1=1; b₃ = 1 + 1 + 1 = 1.

Добавляем проверочные символы к информационным и получаем кодовую комбинацию:

Biр = 1101001.

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

Аi(х) = а_n-1x^n-1 + а_n-2x^n-2 +…+ а₀x⁰

где a_n-1, … коэффициенты полинома принимающие значения 0 или 1. Например, комбинации 1001011 соответствует полином

Аi(х) = 1?x⁶ + 0?x⁵ + 0?x⁴ + 1?x³ + 0?x² + 1?x+1?x⁰ ? x⁶ + x³ + x+1.

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

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

Этапы формирования разрешенной кодовой комбинации разделимого циклического кода Biр(х).

1.  Информационная кодовая комбинация Ai преобразуется из двоичной формы в полиномиальную (Ai(x)).

2.  Полином Ai(x) умножается на х^r,

Ai(x)?x^r

где r количество проверочных разрядов:

r = n — k.

3.  Вычисляется остаток от деления R(x) полученного произведения на порождающий полином:

R(x) = Ai(x)?x^r/G(x).

4.  Остаток от деления (проверочные разряды) прибавляется к информационным разрядам:

Biр(x) = Ai(x)?x^r + R(x).

5.  Кодовая комбинация Bip(x) преобразуется из полиномиальной формы в двоичную (Bip).

Пример 4. Необходимо сформировать кодовую комбинацию циклического кода (7,4) с порождающим полиномом G(x)=х³+х+1, соответствующую информационной комбинации 0110.

1. Преобразуем комбинацию в полиномиальную форму:

Ai = 0110 ? х² + х = Ai(x).

2. Находим количество проверочных символов и умножаем  полученный полином на x^r:

r = n – k = 7 – 4 =3

Ai(x)?x^r = (х² + х)? x³ = х⁵ + х⁴

3. Определяем остаток от деления Ai(x)?x^r на порождающий полином, деление осуществляется до тех пор пока наивысшая степень делимого не станет меньше наивысшей степени делителя:

R(x) = Ai(x)?x^r/G(x)

4. Прибавляем остаток от деления к информационным разрядам и переводим в двоичную систему счисления:

Biр(x) = Ai(x)?x^r+ R(x) = х⁵ + х⁴ + 1? 0110001.

5. Преобразуем кодовую комбинацию из полиномиальной формы в двоичную:

Biр(x) = х⁵ + х⁴ + 1 ? 0110001 = Biр

Как видно из комбинации четыре старших разряда соответствуют информационной комбинации, а три младших — проверочные.

Формирование разрешенной кодовой комбинации неразделимого циклического кода.

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

Biр(x) = Ai(x)?G(x).

Причем умножение можно производить в двоичной форме.

Пример 5, необходимо сформировать кодовую комбинацию неразделимого циклического кода используя данные примера 2, т. е. G(x) = х³+х+1, Ai(x) = 0110, код (7,4).

1. Переводим комбинацию из двоичной формы в полиномиальную:

Ai = 0110? х²+х = Ai(x)

2. Осуществляем деление Ai(x)?G(x)

3. Переводим кодовую комбинацию из полиномиальной форы в двоичную:

Bip(x) = х⁵+х⁴+х³+х ? 0111010 = Bip

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

Матричное представление систематических кодов

Систематические коды, рассмотренные выше (код Хэмминга и разделимый циклический код) удобно представить в виде матриц. Рассмотрим, как это осуществляется.

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

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

2)      нулевая комбинация не должна входить в число исходных комбинаций;

3)      каждая исходная комбинация должна иметь вес не менее кодового расстояния, т. е. W?d₀;

4)      между любыми двумя исходными комбинациями расстояние Хэмминга должно быть не меньше кодового расстояния, т. е. d_ij?d₀.

Производящая матрица имеет вид:

Производящая подматрица имеет k строк и n столбцов. Она образована двумя подматрицами: информационной (включает элементы а_ij) и проверочной (включает элементы b_ij). Информационная матрица имеет размеры k?k, а проверочная — r?k.

В качестве информационной подматрицы удобно брать единичную матрицу E_kk:

Проверочная подматрица G_r,k строится путем подбора различных r-разрядных комбинаций, удовлетворяющих следующим правилам:

1)      в каждой строке подматрицы количество единиц должно быть не менее d₀-1;

2)      сумма по модулю два двух любых строк должна иметь не менее d₀-2 единицы;

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

Пример 6. Необходимо построить производящую матрицу кода Хэмминга способного исправлять 1 ошибку и имеющего n=7. Закодировать с помощью полученной матрицы комбинацию Ai=1101.

Определяем кодовое расстояние:

d₀=2q_{и ош}+1= 2?1+1=3.

Для кодов с d₀=3 количество проверочных разрядов определяется по формуле:

r=log₂(n+1)= log₂8=3.

Определяем разрядность информационной части:

k = n — r = 7 — 4 =3.

Запишем все возможные комбинации проверочной подматрицы: 000, 001, 010, 011, 100, 101, 110, 111. Выберем из этих комбинаций те, что удовлетворяют правилам:

1)      в каждой строке не менее d₀-1, этому условию соответствуют комбинации 011, 101, 110, 111;

2)      сумма двух любых комбинаций по модулю два содержит единиц не менее d₀-2:

3)      записываем проверочную подматрицу:

4)      приписываем полученную подматрицу к единичной и получаем производящую матрицу:

Если произвести определение d₀ для исходных комбинаций полученной матрицы (определив расстояние Хэмминга для всех пар комбинаций), то оно окажется равным 3.

Для кодирования заданной комбинации Ai, необходимо просуммировать те строки матрицы G, которые в информационной части имеют единицу на том месте, на котором они находятся в комбинации Аi. Для заданной комбинации 1101 единичными разрядами являются а₁, а₂, а₄. В матрице G единицы на этих местах имеют строки: первая, вторая и четвертая. Просуммировав их получаем разрешенную комбинацию заданного кода.

Сравнивая полученную кодовую комбинацию Bip с комбинацией полученной примере 3, для которой также использована комбинация Ai=1101, видим что они одинаковы.

Для кода Хэмминга выше были определены правила формирования проверочных символов b_k:

Эти правила можно отобразить в виде проверочной матрицы Н_n,k. Она состоит из n столбцов (соответствует разрядности кодовой комбинации) и r столбцов (соответствует количеству проверочных разрядов кодовой комбинации). В правой части матрицы указываются синдромы, соответствующие ошибкам в проверочных символах, в левой части записываются элементы информационной части комбинации, причем, те элементы, которые участвуют в образовании определенного элемента b_i равны единицы, а те которые не участвуют — нулю.

В данном случае обведенные пунктиром проверочные элементы образуют единичную матрицу. Проверочная матрица позволяет определить ошибочный разряд, поскольку каждый столбец данной матрицы представляет собой синдром соответствующего символа. При этом строки матрицы будут соответствовать разрядам синдрома C_k. Например, согласно приведенной проверочной матрице, синдром соответствующий ошибку в разряде а₁ имеет вид 011, в разряде а₂ — 101, в разряде а₃ — 110, в разряде а₄ — 111, в разряде b₁ — 100, в разряде b₂ — 010, в разряде b₃ — 001. Также с помощью проверочной матрицы легко определить проверочные и символы и сформировать кодовую комбинацию. Например, необходимо сформировать кодовую комбинацию кода Хэмминга (7,4) соответствующую информационным символам 1101.

В соответствии с проверочной матрицей определяем b_i:

b₁ = 1 + 0 + 1 = 0; b₂ = 1 + 0 + 1=0; b₃ = 1 + 1 + 1 = 1.

Добавляем проверочные символы к информационным и получаем кодовую комбинацию:

Biр = 1101001.

Также проверочную матрицу можно построить и другим способом. Для этого сначала строится единичная матрица Е_r. К которой слева приписывается подматрица D_k,r. Каждая строка этой подматрицы соответствует столбцу проверочных разрядов подматрицы С_r,k производящей матрицы G_n,k.

Такое преобразование строк матрицы в столбцы называется транспонированием.

В результате получаем

Декодирование циклических кодов

При декодировании таких кодов (разделимых и неразделимых) используется Синдромный способ. Вычисление синдрома осуществляется в три этапа:

1. принятая комбинация Bip’ преобразуется их двоичной формы в полиномиальную (Bip(x));

2. осуществляется деление Bip(x) на порождающий полином G(x) в результате чего определяется синдром ошибки C(x) (остаток от деления);

3. синдром ошибки преобразуется из полиномиальной формы в двоичную;

4. По проверочной матрице или таблице синдромов определяется ошибочный разряд;

5. Ошибочный разряд в Bip’(x) инвертируется;

6. Исправленная комбинация преобразуется из полиномиальной формы в двоичную Bip.

делением принятой кодовой комбинации Biр’(x) на порождающий полином G(x), который заранее известен на приеме. Остаток от деления и является синдромом ошибки С(х).

Мажоритарное декодирование циклических кодов

Мажоритарное декодирование может применятся только для декодирования систематических кодов (кода Хэмминга, циклического разделимого кода). Рассмотрим мажоритарное декодирование на примере циклического кода.

		Обноружение ошибок
		Исправление ошибок
		Коррекция ошибок
		Назад

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

Синдром	001	010	011	100	101	110	111
Конфигурация ошибок	0000001	0000010	0000100	0001000	0010000	0100000	1000000
Ошибка в символе	m1	m2	i4	m1	i1	i3	i2

Предложите, как улучшить StudyLib

(Для жалоб на нарушения авторских прав, используйте

другую форму
)