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

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

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

Любой символ а_i
выражается d (минимальное кодовое
расстояние) различными независимыми
способами в виде линейных комбинаций
других символов. При этом может
использоваться тривиальная проверка
а_i
= а_i.
Результаты вычислений подаются на
соответствующий этому символу мажоритарный
элемент. Последний представляет собой
схему, имеющую d входов и один выход, на
котором появляется единица, когда
возбуждается больше половины его входов,
и нуль, когда возбуждается число таких
входов меньше половины. Если ошибки
отсутствуют, то проверочные равенства
не нарушаются и на выходе мажоритарного
элемента получаем истинное значение
символа. Если число проверок d2s+
1 и появление ошибки кратности s и менее
не приводит к нарушению более s проверок,
то правильное решение может быть принято
по большинству неискаженных проверок.
Чтобы указанное условие выполнялось,
любой другой символ a_j(ji)
не должен входить более чем в одно
проверочное равенство. В этом случае
мы имеем дело с системойразделенных
проверок.

Пример 7.12.
Построим
систему разделенных проверок для
декодирования информационных символов
рассмотренного ранее группового кода
(8,2).

Решение.
Поскольку
код рассчитан на исправление любых
единичных и двойных ошибок, число
проверочных равенств для определения
каждого символа должно быть не менее
5. Подставив в равенства (7.2 а) и (7.2 б)
значения а₈,
полученные из равенств (7.2 д) и (7.2 е) и
записав их относительно a₅
совместно с равенствами (7.2 в) и (7.2 г) и
тривиальным равенством a₅
= a₅,
получим следующую систему разделенных
проверок для символа a₅:

a₅
= a₆a_1,

a₅
= a₇a_2,

а₅
= а₃,

а₅
= a₄,

а₅
= а₅.

Для символа a₈
систему разделенных проверок строим
аналогично:

a₈
= a₃a_1,

a₈
= a₄a_2,

a₈
= а₆,

a₈
= a₇,

a₈
= а₈.

7.13. Матричное представление линейных кодов

Матрицей
размерности
ln
называют упорядоченное множество ln
элементов, расположенных в виде
прямоугольной таблицы с l
строками и n
столбцами:

Транспонированной
матрицей к
матрице А
называют матрицу, строками которой
являются столбцы, а столбцами строки
матрицы А:

Матрицу размерности
nn
называют квадратной
матрицей порядка n.
Квадратную матрицу, у которой по одной
из диагоналей расположены только
единицы, а все остальные элементы равны
нулю, называют единичной
матрицей I.
Суммой двух матриц А
|а_ij|
и В|b_ij|
размерности ln
называют матрицу размерности ln:

А+В|а_ij|
+ |b_ij||а_ij+b_ij|.

Умножение матрицы
А
|а_ij|
размерности ln
на скаляр с
дает матрицу размерности ln:
сА

c
|а_ij||c
а_ij|.

Матрицы А
|а_ij|
размерности ln
и В|b_jk|
размерности nm
могут быть перемножены, причем элементами
c_ik
матрицы — произведения размерности
lm
являются суммы произведений элементов
l-й
строки матрицы А
на соответствующие элементы k-го
столбца матрицы В:

c_ik=

В теории кодирования
элементами матрицы являются элементы
некоторого поля GF(P), а строки и столбцы
матрицы рассматриваются как векторы.
Сложение и умножение элементов матриц
осуществляется по правилам поля GF(P).

Пример 7.13.
Вычислим
произведение матриц с элементами из
поля GF (2):

Элементы c_ik
матрицы произведения М
= M₁M₂
будут равны:

c₁₁
= (011) (101) = 0 + 0 + 1 = 1

c₁₂
= (011) (110) = 0 + 1 + 0 = 1

c₁₃
= (011) (100) = 0 + 0 + 0 = 0

c₂₁
= (100) (101) = 1 + 0 + 0 = 1

c₂₂
= (100) (110) = 1 + 0 + 0 = 1

c₂₃
= (100) (100) = 1 + 0 + 0 = 1

c₃₁
= (001) (101) = 0 + 0 + 1 = 1

c₃₂
= (001) (110) = 0 + 0 + 0 = 0

c₃₃
= (001) (100) = 0 + 0 + 0 = 0

Следовательно,

Зная закон построения
кода, определим все множество разрешенных
кодовых комбинаций. Расположив их друг
под другом, получим матрицу, совокупность
строк которой является подпространством
векторного пространства n-разрядных
кодовых комбинаций (векторов) из элементов
поля GF(P). В случае двоичного (n,
k)-кода
матрица насчитывает n
столбцов и 2^k—1
строк (исключая нулевую). Например, для
рассмотренного ранее кода (8,2), исправляющего
все одиночные и двойные ошибки, матрица
имеет вид

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

Совокупность
векторов V₁,
V₂,
V₃,
…, V_n
называют линейно
зависимой,
когда существуют скаляры с₁,..с_n
(не все
равные нулю), при которых

c₁V₁
+ c₂V₂+…+
c_nV_n=
0

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

Среди 2^k
– 1 ненулевых
двоичных кодовых комбинаций — векторов
их только k. Например, для кода (8,2)

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

Если порождающая
матрица содержит k строк по n
элементов поля GF(q), то код называют (n,
k)-кодом.
В каждой комбинации (n,
k)-кода
k информационных символов и n
– k проверочных. Общее число разрешенных
кодовых комбинаций (исключая нулевую)
Q = q^k-1.

Зная порождающую
матрицу кода, легко найти разрешенную
кодовую комбинацию, соответствующую
любой последовательности А_ki
из k информационных символов.

Она получается в
результате умножения вектора А_ki
на порождающую матрицу М_n,k:

А_ni=А_ki•М_n,k.

Найдем, например,
разрешенную комбинацию кода (8,2),
соответствующую информационным символам
a₅=l,
a₈
= 1:

.

Пространство строк
матрицы остается неизменным при
выполнении следующих элементарных
операций над строками: 1) перестановка
любых двух строк; 2) умножение любой
строки на ненулевой элемент поля; 3)
сложение какой-либо строки с произведением
другой строки на ненулевой элемент
поля, а также при перестановке столбцов.

Если образующая
матрица кода M₂
получена из образующей матрицы кода M₁
с помощью элементарных операций над
строками, то обе матрицы порождают один
и тот же код. Перестановка столбцов
образующей матрицы кода приводит к
образующей матрице эквивалентного
кода. Эквивалентные коды весьма близки
по своим свойствам. Корректирующая
способность таких кодов одинакова.

Для анализа
возможностей линейного (n,
k)-кода,
а также для упрощения процесса кодирования
удобно, чтобы порождающая матрица (М_n,k)
состояла из двух матриц: единичной
матрицы размерности k
k и дописываемой справаматрицы-дополнения
(контрольной подматрицы) размерности
k • (n
– k), которая соответствует n
– k проверочным разрядам:

(7.3)

Разрешенные кодовые
комбинации кода с такой порождающей
матрицей отличаются тем, что первые k
символов в них совпадают с исходными
информационными, а проверочными
оказываются (n — k) последних символов.
Действительно, если умножим вектор-строку
A_k,i
= = (a₁
a₂…a_i…a_k)
на матрицу М_n,k=
[I_kP_k,n—k],
получим вектор

A_n,i
= (a₁a₂…a_i…a_k…a_k+1…a_j…a_n),

где проверочные
символы а_j(k
+1jn)
являются линейными комбинациями
информационных:

(7.4)

Коды, удовлетворяющие
этому условию, называют систематическими.
Для каждого линейного кода существует
эквивалентный систематический код. Как
следует из (7.3), (7.4), информацию о способе
построения такого кода содержит
матрица-дополнение. Если правила
построения кода (уравнения кодирования)
известны, то значения символов любой
строки матрицы-дополнения получим,
применяя эти правила к символам
соответствующей строки единичной
матрицы.

Пример 7.14.
Запишем матрицы I_k,
Р_k,n—k_и
M_n,k
для двоичного кода (7,4).

Единичная матрица
на четыре разряда имеет вид

Один из вариантов
матрицы дополнения можно записать,
используя соотношения (4.1)

Тогда для двоичного
кода Хэммннга имеем:

Запишем также
матрицу для систематического кода
(7,4):

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

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

Так как минимальное
кодовое расстояние d для линейного кода
равно минимальному весу его ненулевых
векторов, то в матрицу-дополнение должны
быть включены такие k строк, которые
удовлетворяли бы следующему общему
условию: вектор-строка образующей
матрицы, получающаяся при суммировании
любых l
(1lk)
строк, должна содержать не менее d – l
отличных от нуля символов.

Действительно,
при выполнении указанного условия любая
разрешенная кодовая комбинация,
полученная суммированием l
строк образующей матрицы, имеет не менее
d ненулевых символов, так как l
ненулевых символов она всегда содержит
в результате суммирования строк единичной
матрицы. Синтезируем таким путем
образующую матрицу двоичного
систематического кода (7,4) с минимальным
кодовым расстоянием d = 3. В каждой
вектор-строке матрицы-дополнения
согласно сформулированному условию
(при l=1)
должно быть не менее двух единиц. Среди
трехразрядных векторов таких имеется
четыре: 011, 110, 101, 111.

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

Нетрудно убедиться,
что при суммировании нескольких строк
такой матрицы (l>1)
получим вектор-строку, содержащую не
менее d=3 ненулевых символов.

Имея образующую
матрицу систематического кода
М_n,k=
[I_kP_k,n—k],
можно построить так называемую проверочную
(контрольную) матрицу Н
размерности (n
– k)n:

При умножении
неискаженного кодового вектора А_ni
на матрицу, транспонированную к матрице
Н,
получим вектор, все компоненты которого
равны нулю:

Каждая компонента
S_j
является результатом проверки
справедливости соответствующего
уравнения декодирования:

В общем случае,
когда кодовый вектор А_ni
=(a_1,
a₂,…,
a_i,…,a_k,a_k+1,…,a_j,…,a_n)
искажен вектором ошибки
ξ_ni
=(ξ_1,
ξ₂,…,
ξ_i,…,ξ_k,aξ_k+1,…,ξ_j,…,ξ_n),
умножение вектора (А_ni
+ ξ_ni)
на матрицу Н^т
дает ненулевые компоненты:

Отсюда видно, что
S_j(k
+1jn)
представляют собой символы, зависящие
только от вектора ошибки, а вектор S
= (S<sub>k
+ 1</sub>, S<sub>k
+ 2</sub>, …,, S_j,
…, S_n)
является не чем иным, как опознавателем
ошибки (синдромом).

Для двоичных кодов
(операция сложения тождественна операции
вычитания) проверочная матрица имеет
вид

Пример 7.15.
Найдем
проверочную матрицу Н
для кода (7,4) с образующей матрицей М:

Определим синдромы
в случаях отсутствия и наличия ошибки
в кодовом векторе 1100011.

Выполним
транспонирование матрицы P_4,3

Запишем проверочную
матрицу:

Умножение на Н^т
неискаженного кодового вектора 1100011
дает нулевой синдром:

При наличии в
кодовом векторе ошибки, например, в 4-м
разряде (1101011) получим:

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

Задание
1

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

Код
предусматривает возможность посылки N = 64  сообщений,
тогда:

; 

n_u=6

n_k=4

n=n_u+n_k=10

Построим
производящую матрицу G, она представляется слиянием
матриц И и П.

В качестве И
выбирают единичную матрицу размером n_u:

Определим вес
строк матрицыП:

W_П > = d₀ —
1

d₀ = 3

Следовательно:
W_П  ≥ 2, исходя из этого, составим матрицу
П:

Тогда
производящая матрица будет иметь вид:

Задание
2

Привести
пример 10 кодовых комбинаций.

Кодирование сообщений:

1) 19 в
двоичной системе: 010011

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

2 – 1110

5 – 0111

6 – 1100

      0101

Следовательно,
линейный групповой код имеет вид: 0100110101

2) 20 в
двоичной системе: 010100

2 – 1110

4 – 1011

      0101

Линейный
групповой код: 0101000101

3) 35 в
двоичной системе имеет вид: 100011

1 – 1111

5 – 0111

6 – 1100

      0100

Линейный
групповой код: 1000110100

4) 38 в
двоичной системе: 100110

1 – 1111

4 – 1011

5 – 0111

      0011

Линейный
групповой код: 1001100011

5) 44 в
двоичной системе: 101100

1 – 1111

3 – 1101

4 – 1011

                  1001

Линейный
групповой код: 1011001001

6) 47 в
двоичной системе: 101111

1 – 1111

3 – 1101

4 – 1011

5 – 0111

6 – 1100

      0010

Линейный
групповой код: 1011110010

7) 49 в
двоичной системе: 110001

1 – 1111

2 – 1110

6 – 1100

      1101

Линейный
групповой код: 1100011101

8) 55 в
двоичной системе: 110111

1 – 1111

2 – 1110

4 – 1011

5 – 0111

6 – 1100

      0001

Линейный
групповой код: 1101110001

9) 56 в
двоичной системе: 111000

1 – 1111

2 – 1110

3 – 1101

      1100

Линейный
групповой код: 1110001100

10) 63
в двоичной системе: 111111

1 – 1111

2 – 1110

3 – 1101

4 – 1011

5 – 0111

6 – 1100

      1100

Линейный
групповой код: 1111111100

Задание
3

Показать процесс исправления ошибки в заданном разряде k .

Для
исправления одинарной ошибки построим матрицу Н, которая получается путем
транспонирования матрицы П и присоединения к ней единичной матрицы размерностью
n_k:

Покажем процедуру
исправления одиночной ошибки на примере сообщения 60:

Отправленное
сообщение:        1111000111

Принятое сообщение:               
1111001111

т.е. имеется
ошибка в седьмом разряде.

Проведем
проверки:

1)  Для
первой проверки берем P₁ и те разряды из
информационной части кода, которые совпадают с ненулевыми разрядами первого
столбца матрицы П:

S₁=P₁+а1+а2+а3+а4+а6=1+1+1+1+1+0=1

По аналогии
проводим остальные проверки.

2)  S₂=P₂+а1+а2+а3+а5+а6=1+1+1+1+0+0=0

3)  S₃=P₃+а1+а2+а4+а5=1+1+1+1+0=0

4)  S₄=P₄+а1+а3+а4+а5=1+1+1+1+0=0

В результате
получаем вектор S= 1000

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

Индивидуальное задание по Теории информации

Подготовил В.С. Прохоров

Построить групповой корректирующий код объёмом 9 слов. Код должен обеспечивать исправление одиночных и обнаружение двойных ошибок.

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

Определим число информационных разрядов кода из соотношения

,

где Q – требуемый объём кода. В нашем случае Q=9, поэтому

Отсюда получаем .

Далее находим число n из неравенства

Подставляем и подбором находим минимальное n, удовлетворяющее неравенству. В нашем случае

.

Далее мы должны составить таблицу опознавателей. Для этого необходимо ввести понятие вектора ошибок и опознавателя. Вектор ошибок это n-разрядная двоичная последовательность, имеющая единицы во всех разрядах, подвергшихся искажению, и нули в остальных разрядах. (Пример: искажению подверглись два младших разряда 6-разрядного сообщения — тогда вектор ошибки будет выглядеть как 000011), а опознаватель – некоторая сопоставленная этому вектору контрольная последовательность символов. В нашем случае векторы ошибок имеют разрядность 7 бит, так как , опознаватели имеют разрядность 3 бит, так как . Опознаватели рекомендуется записывать в порядке возрастания (нулевую комбинацию не используем).

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

Выбираем из таблицы строки, где опознаватели имеют в первом (младшем) разряде единицу. Это строки 1, 3, 5 и 7. Тогда первое проверочное равенство будет выглядеть так:

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

Это строки 2, 3, 6, 7.

Тогда второе проверочное правило выглядит так:

И, наконец выбираем строки, где опознаватели имеют единицу в третьем разряде. Это строки 4, 5, 6, 7. Следовательно третье проверочное равенство выглядит так:

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

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

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

Используя правила построения корректирующего кода (*), построим таблицу разрешённых комбинаций группового кода объёмом 9 слов, способного исправлять все одиночные и обнаруживать двойные ошибки. В колонку «безызбыточный код» записываем девять (по заданию Q=9) комбинаций по возрастанию (нулевую комбинацию не используем).

Все колонки, кроме , , и , содержимое которых определяется формулами (*), заполняем цифрами из безызбыточного кода:

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

Перейдём к построению функциональной схемы кодирующего устройства (см. соответствующий рисунок ниже). Назначение кодирующего устройства – внесение избыточности в код по заданным нами правилам. Схему строим на основании равенств (*). На схеме используется логический элемент «сумматор по модулю два», обозначенный М2. На схеме имеются два регистра, построенные на D-триггерах. Один из них содержит безызбыточный код и имеет разрядность 4 бит, так как , а другой содержит избыточный код и имеет разрядность 8 бит, так как . Принцип работы схемы таков: по сигналу синхронизации на k-разрядный регистр поступает кодовая комбинация, подлежащая кодированию. Затем с помощью сумматоров эта комбинация кодируется (вносится избыточность). Сумматор С1 реализует первое равенство из (*), сумматор С2 – второе, С3 – третье, а С4 – четвёртое. И, наконец, по сигналу синхронизации полученный избыточный код записывается в 8-разрядный регистр. Далее начинается кодирование следующей комбинации.