LEKTsIYa_9
.pdf
1
ЛЕКЦИЯ № 9.
Пусть Ci и C j - два кодовых слова в (n, k) кодовом блоке. Мера разницы между Ci , C j - число позиций, в которых они различаются. Эта мера называется
расстоянием Хемминга |
и |
обозначается di, j , причем 0 di, j |
n , |
i j . |
Минимальное кодовое расстояние определяется следующим образом: |
|
|||
dmin |
|
min {di, j } |
|
(6.2) |
|
i, j |
1,2,..., M |
|
|
|
|
Код |
|
|
Линейный |
Нелинейный |
|
|
|
Рассмотрим два кодовых |
слова Ci , C j и скалярные величины |
1 , 2 . Код |
||
называется линейным, если 1Ci 2C j тоже является кодовым словом из (n, k) блока. Значит, линейный код должен содержать кодовое слово, состоящее из одних нулей. Поэтому код с постоянным весом – нелинейный. Пусть Ci - линейный двоичный блоковый код, i 1,2,..., M . C1 (0.....0)1 n - кодовое слово из
нулей, wi |
- вес i - го кодового слова. Тогда wi |
- расстояние Хемминга между |
Ci и C1 . В результате имеем: |
|
|
|
dmin min{wi } , |
(6.3) |
|
i 1 |
|
так как |
di, j равно весу разности Ci C j , а разность эквивалентна сумме по |
|
модулю 2, но Ci C j - тоже кодовое слово с весом, включенным в набор {wi } .
Порождающая и проверочная матрица.
Пусть X i (xi1 , xi 2 ,....., xik )1 k |
- вектор из |
k информационных бит, |
|
Ci (ci1 , ci 2 ,..., cin )1 n - вектор помехоустойчивого кода. Тогда |
|||
X i |
|
|
Ci |
Кодер (G) |
|
||
|
|
|
|
Ci X i G |
(6.4) |
Gk n - порождающая матрица кода.
g |
g |
|
|
11 |
12 |
G |
|
|
|
|
gk 2 |
gk1 |
||
2
g |
|
|
|
|
|
|
g |
|
|||||
|
1n |
|
1 |
|
. Если выражение (6.4) раскрыть, то |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
gkn |
gk |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
g |
|
|
|
|
|
|
||
C |
|
x |
|
x |
|
1 |
|
x |
x |
|
, т.е. произвольное кодовое слово – |
||
i |
|
|
|
g |
g |
k |
|||||||
|
i1 |
|
|
ik |
|
|
i1 1 |
ik |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
gk |
|
|
|
|
|
|
|
|
линейная комбинация векторов |
|
}, l 1,2,...., k из порождающей матрицы G . |
|||||||||||
{gl |
|||||||||||||
Вектора |
|
|
должны быть линейно независимыми. |
||||||||||
{gl |
} |
||||||||||||
Система векторов |
|
} называется линейно зависимой, если хотя бы один из |
|||||||||||
{gl |
|||||||||||||
этих векторов является линейной комбинацией остальных векторов и линейно независимой в противоположном случае.
Любую порождающую матрицу G (n, k) - кода путем проведения операций над строками и столбцами можно свести к систематической форме:
|
G k k |
|
Pk (n k ) , |
(6.5) |
|||
где kk - единичная матрица размерностью k k , Pk (n k ) |
- матрица дополнение, |
||||||
которая |
определяет n k избыточных |
|
(проверочных) |
символов. Тогда по |
|||
формуле |
(6.4) получим систематический код, у которого первые k бит |
||||||
информационные, остальные n k |
проверочные. |
|
|||||
Для декодирования используется проверочная матрица H(n k ) n , причем, |
|||||||
|
C H T |
0 |
|
, |
|
||
|
i |
|
|
1 (n k ) |
|
(6.6) |
|
|
GHT |
|
0 |
|
. |
||
|
k (n k ) |
|
|||||
|
|
|
|
|
|
|
|
Если линейный двоичный (n, k) код систематический, то проверочная матрица имеет вид:
H PT |
(n k ) (n k ) |
|
|
(6.7) |
Коды Хемминга. |
|
|
|
|
Двоичные коды Хемминга: |
(n, k ) (2m 1,2m 1 m) , |
где |
m - |
целое |
положительное число. Если m 3 , то получим (7,4) код. |
n 2m 1 столбцов |
|||
матрицы H состоят из всех |
возможных двоичных векторов |
с |
n k m |
|
элементами, исключая нулевой вектор. |
|
|
|
|
3
Пример. Рассмотрим систематический (7,4) код Хемминга с проверочной
|
1 1 1 |
0 |
1 |
0 |
0 |
|
1 1 1 |
0 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
матрицей |
H |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
. |
Здесь |
PT |
0 |
1 |
1 |
1 |
|
- |
|
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
|
1 |
1 |
0 |
1 |
|
|
|
|
3 7 |
|
|
3 4 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
транспонированная матрица дополнение. Тогда порождающая матрица имеет
|
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
||
|
|
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
вид: |
G |
|
|
. Пусть X i |
(xi1 , xi 2 , xi3 , xi 4 ) |
информационное |
||||||||
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
||||||
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
||
|
|
|
4 7 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
кодовое слово, которое поступает на вход кодера. Далее по формуле (6.4) получим помехоустойчивое кодовое слово:
1 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
(ci1 , ci 2 , ci3 , ci 4 , ci5 , ci6 , ci7 ) , |
|||||||
Ci (xi1 , xi 2 , xi3 , xi 4 ) |
0 0 1 |
0 |
1 |
1 |
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|||||||
где ci1 xi1 , ci 2 xi 2 , ci3 xi3 , ci 4 xi 4 , ci5 xi1 xi 2 xi3 , ci 6 xi 2 xi3 xi 4 , ci 7 xi1 xi 2 xi 4 .
Кодер систематического кода (7,4).
X i |
xi 3 |
xi 2 xi 4 xi1 |
|
Ci
ci 7 ci 6 ci5
Кодер использует 4 –х битовый и 3-х битовый регистр сдвига, а также 3 сумматора по модулю 2.
Замечание. При m 1 для (n, k) кода Хемминга dmin 3 .
4
|
|
|
|
6.2. Оптимальное декодирование линейных блоковых кодов. |
|||||
Блоковый (n, k) код способен обнаружить dmin 1 ошибку и исправить |
|||||||||
1 |
(d |
|
1) |
ошибок, где |
|
|
- наибольшее целое, содержащееся в аргументе. |
||
|
|
min |
|||||||
|
|
|
|
|
|||||
2 |
|
|
|
|
|
|
|
||
Пусть Ci - переданное кодовое слово, Y Ci |
e - принятое кодовое слово, где |
||||||||||
e - вектор ошибок. Тогда |
|
|
|
|
|
|
|
|
|||
|
YH T (C e)H T C H T eHT eHT S , т.к. C H T |
0 |
. |
|
|
||||||
|
|
|
i |
i |
|
i |
1 (n k ) |
|
|
|
|
Произведение |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
YH T eHT S |
|
|
|
|
|
(6.8) |
|
называется синдромом. S |
- характеристика образцов ошибок. Существует 2n |
||||||||||
возможных образцов ошибок, но только 2n k |
синдромных. Следовательно, |
||||||||||
разные образцы ошибок приводят к одинаковым синдромам. |
|
|
|
||||||||
Для декодирования составляется таблица размером , 2k 2n k которая |
|
|
|||||||||
называется стандартным расположением для заданного кода. |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
||
C1 |
|
C2 |
|
C3 |
|
|
|
C |
k |
||
|
|
|
|
|
|
|
|
|
|
2 |
|
e2 |
|
C2 e2 |
|
C3 e2 |
|
|
|
C k e2 |
|||
|
|
|
|
|
|
|
|
|
2 |
|
|
e |
3 |
|
C2 e3 |
|
C3 e3 |
|
|
|
C |
k e |
|
|
|
|
|
|
|
|
|
2 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
e2n k |
|
C2 e2n k |
|
C3 e2n k |
|
|
|
C2k e2n k |
|||
Первый столбец – образцы ошибок, первая строка – все возможные кодовые слова, начиная с кодового слова, состоящего из одних нулей. Каждую строку называют смежным классом, а первый столбец – лидеры смежных классов.
Таким образом, смежный класс состоит из всевозможных принимаемых кодовых слов, получающегося от частного образца ошибки (лидера смежного класса).
|
|
|
|
|
|
|
|
Пример. Задан код (5,2) с порождающей матрицей G |
1 |
0 |
1 |
0 |
1 |
||
|
|
|
|
|
. |
||
|
0 |
1 |
0 |
1 |
|
|
|
|
1 |
||||||
1 |
0 |
1 |
0 |
0 |
|
||
|
|
|
|
|
|
|
|
Тогда 2k 22 4, 2n k 25 2 8 , проверочная матрица H |
0 |
1 |
0 |
1 |
0 |
. |
|
|
1 |
1 |
0 |
0 |
1 |
|
|
|
|
||||||
5
Стандартное расположение (таблица декодирования):
|
|
|
Таблица 1. |
X1 (00) |
X 2 (01) |
X 3 (10) |
X 4 (11) |
|
|
|
|
00000 |
01011 |
10101 |
11110 |
00001 |
01010 |
10100 |
11111 |
00010 |
01001 |
10111 |
11100 |
00100 |
01111 |
10001 |
11010 |
01000 |
00011 |
11101 |
10110 |
10000 |
11011 |
00101 |
01110 |
11000 |
10011 |
01101 |
00110 |
10010 |
11001 |
00111 |
01100 |
Образцы ошибок с весом 2 были выбраны так, чтобы соответствующие ей синдромы отличались от тех, которые соответствуют одиночным ошибкам.
Для заданного кода минимальное кодовое расстояние dmin 3 . Его можно определить по формуле (6.3) для разрешенных кодовых комбинаций (первая строка таблицы 1), исключая из рассмотрения нулевое кодовое слово.
Таблица 2.
ei |
Si |
|
|
00000 |
000 |
00001 |
001 |
00010 |
010 |
00100 |
100 |
01000 |
011 |
10000 |
101 |
11000 |
110 |
10010 |
111 |
Пусть принято кодовое слово Y . Находим синдром S YH T , далее выбираем соответствующий этому синдрому наиболее правдоподобный вектор ошибки eˆ (по таблице 2). Тогда оценка передаваемого кодового слова
ˆ |
ˆ |
(6.9) |
C Y e |
||
6
Структурная схема декодера.
Y |
S |
ˆ |
ˆ |
e |
C |
||
YH T |
Выбор |
|
|
вектора |
|
|
|
|
ошибки |
|
|
Данный код может обнаружить 2 ( dmin 1 3 1 2 ) ошибки, исправить все
одиночные ошибки ( |
1 |
(dmin |
1) |
1) и только 2 двойные, синдромы которых |
||
|
|
|||||
|
|
|
|
|||
|
2 |
|
|
|
||
отличаются от синдромов одиночных ошибок. Подтвердим сказанное на примере.
Пусть принимаемое кодовое слово Y (11111) , где Ci (01011 ) C2 , e (10100 ) .
|
1 |
0 |
1 |
|
|
|
|
|
0 |
1 |
1 |
|
|
|
|
|
|
|||
Тогда S (11111) |
1 |
0 |
0 |
|
(001) . Полученному синдрому соответствует вектор |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
|
|
|
|
0 |
0 |
1 |
|
|
ошибки |
|
|
|
|||
e (00001) e1 . По (6.9) находим оценку переданного кодового слова |
||||||
|
ˆ |
|
|
|
|
|
ˆ |
|
|
(11110) C4 C2 . Т.е получаем ошибку декодирования. |
|||
C (11111) (00001) |
||||||
Вывод. Алгоритм (6.9) работает по критерию максимального
правдоподобия (МП) или по критерию минимального расстояния. Он обеспечивает минимальную вероятность ошибки декодирования в двоичном симметричном канале связи.