Конспект лекции по ТЭС
.pdfЕсли принятая комбинация y будет принадлежать нижней части таблицы, где (ei ) t , то у декодера есть два варианта:
1)отказаться от её декодирования и объявить об обнаружении ошибки (алгоритм неполного декодирования);
2)декодировать её в соответствующую кодовую комбинацию, принадлежащую верхней строке (алгоритм полного декодирования).
Если используется полный алгоритм, то декодер исправит все комбинации с t и менее ошибочными символами и часть комбинаций с большим числом ошибочных символов.
Например, для кода (5,2) таблица декодирования будет следующей:
0 0 0 0 0 |
0 1 1 0 1 |
1 0 1 1 1 |
1 1 0 1 0 |
|
0 0 0 0 |
0 1 1 1 |
1 0 0 0 0 |
1 1 1 0 1 |
0 0 1 1 1 |
0 1 0 1 0 |
|
1 0 0 0 |
1 1 1 1 |
0 1 0 0 0 |
0 0 1 0 1 |
1 1 1 1 1 |
1 0 0 1 0 |
|
0 1 0 0 |
0 0 1 1 |
0 0 1 0 0 |
0 1 0 0 1 |
1 0 0 1 1 |
1 1 1 1 0 |
Пример |
0 0 1 0 |
0 1 0 1 |
0 0 0 1 0 |
0 1 1 1 1 |
1 0 1 0 1 |
1 1 0 0 0 |
кода |
0 0 0 1 |
0 1 1 0 |
0 0 0 0 1 |
0 1 1 0 0 |
1 0 1 1 0 |
1 1 0 1 1 |
(4,1) |
1 0 0 1 |
1 1 1 0 |
0 0 1 1 0 |
0 1 0 1 1 |
1 0 0 0 1 |
1 1 1 0 0 |
|
1 0 1 0 |
1 1 0 1 |
0 0 0 1 1 |
0 1 1 1 0 |
1 0 1 0 0 |
1 1 0 0 1 |
|
1 1 0 0 |
1 0 1 1 |
Она содержит mn 25 |
32 комбинации длины n 5 . |
|
|
Приняв одну из ошибочных комбинаций, декодер по таблице легко декодирует её в ближайшую по Хэммингу кодовую комбинацию. Далее, если код систематический, то декодер отделяет информационные символы и выдаёт их получателю. Если код несистематический, то информационные символы определяются по таблице кодирования.
Синдромное декодирование или декодирование с использованием проверочной матрицы
При большом числе кодовых комбинаций можно значительно сократить таблицу
декодирования, если использовать проверочную матрицу кода |
H , с помощью которой |
вычисляют синдром: |
|
s HT y . |
(37) |
Поскольку |
|
y ci e , |
(38) |
то синдром s полностью определяется комбинацией ошибок: |
|
s HT y HTci HTe HTe . |
(39) |
Различные комбинации ошибок определяют различные синдромы. При синдромном декодировании достаточно определить все mn k синдромов.
Например, используя проверочную матрицу кода (5,2),
1 |
1 |
|
|
1 |
||||
1 |
0 |
|
|
1 |
||||
H 1 |
|
|
|
|
|
|
|
0 , |
|
0 |
|
||||||
0 |
1 |
|
|
0 |
||||
|
0 |
|
|
|
||||
0 |
|
|
1 |
по формуле s HTeˆ вычислим всевозможные синдромы:
ˆ T |
(e0 , e1, e2, e3 , e4 ) |
s |
T |
(s0 , s1 |
, s2 ) |
e |
|
||||
|
0 0 0 0 0 |
|
|
0 0 0 |
|
|
1 0 0 0 0 |
|
|
1 1 1 |
|
|
0 1 0 0 0 |
|
|
1 0 1 |
|
|
0 0 1 0 0 |
|
|
1 0 0 |
|
|
0 0 0 1 0 |
|
|
0 1 0 |
|
|
0 0 0 0 1 |
|
|
0 0 1 |
|
|
0 0 1 1 0 |
|
|
1 1 0 |
|
|
0 0 0 1 1 |
|
|
0 1 1 |
|
130
Число различных синдромов равно mn k 25 2 8 .
Чтобы декодировать принятую комбинацию в кодовую комбинацию необходимо:
1)вычислить синдром s ;
2)по таблице синдромов определить соответствующую комбинацию ошибок eˆ ;
3)по формуле
cˆi y eˆ |
(40) |
находят возможную переданную кодовую комбинацию.
Возможности кода по обнаружению и исправлению ошибок
Режим обнаружения работы декодера используется только для обнаружения ошибок. Предполагается, что при обнаружении ошибок декодер делает переспрос принятой с ошибками кодовой комбинации для её повторного приёма. В режиме исправления ошибок декодер только исправляет ошибки в принятой кодовой комбинации.
Обнаруживающая способность кода определяется как максимальное число
ошибочных символов, которое гарантированно обнаруживается кодом: |
|
qо dmin 1 . |
(41) |
При этом, число различных комбинаций ошибок, содержащих от 1 до qo ошибочных |
|
qo |
|
символов, равно Cni (m 1)i . В действительности код позволяет обнаружить |
mn mk |
i 1
различных ошибочных (запрещённых) комбинаций.
Исправляющая способность кода – это максимальное число ошибочных символов, которое гарантированно позволяет исправить код. Если минимальное расстояние кода равно dmin , то исправляющая способность кода равна
|
|
|
dmin |
1 |
|
|||
|
|
|
t |
|
|
|
. |
(42) |
|
|
|
|
2 |
|
|||
|
t qo , то |
|
|
|
|
|
||
Поскольку |
t и |
менее |
ошибочных символов кодом обнаруживается и |
|||||
исправляется, а |
t 1 , t 2 |
и т.д. |
до qo |
ошибочных символов будет обнаружено, |
но не |
|||
исправлено. |
|
|
|
|
|
|
|
|
Декодирование при стираниях
Демодулятор может быть сконструирован таким образом, что если символ принят неоднозначно (из-за действия помех или из-за кратковременных сбоев), то он объявляет его стёртым символом. Стёртый символ – это дополнительный символ алфавита, положение которого в принятой комбинации точно известно, но неизвестно его значение. Стёртые символы отличаются от ошибочных тем, что у ошибочных символов неизвестно ни положение, ни значение ошибки.
Если минимальное расстояние кода dmin , то любая комбинация из |
или меньшего |
числа стёртых символов может быть исправлена при условии, что |
|
dmin . |
(43) |
131
Помехоустойчивость блочных кодов
Помехоустойчивость различных кодов, исправляющих или обнаруживающих ошибки,
характеризуется или оценивается вероятностью ошибки декодирования кодовой комбинации Pдек.к.к , вероятность необнаруженной ошибочной кодовой комбинации
Pн.о.к.к и вероятностью ошибки на бит pb .
Режим исправления ошибок
Алгоритм неполного декодирования. Если декодер исправляет t и менее ошибочных символов (алгоритм неполного декодирования), то вероятность того, что декодер, анализируя принятую комбинацию с ошибками, вместо переданной выдаст в качестве решения другую кодовую комбинацию (вероятность ошибки декодирования кодовой комбинации), равна
|
|
|
|
|
|
mk 1 |
|
|
|
|
|
|
|
|
|
Pдек.к.к |
1 Pпр.дек |
1 P(ci )P d (y, ci ) t | ci |
. |
(44) |
|||||||||
|
|
|
|
|
|
i 0 |
|
|
|
|
|
|
|
|
|
Для линейного кода P d (y, ci ) t | ci P (e) t . Тогда |
|
|
|||||||||||
|
|
mk 1 |
|
|
|
|
|
|
|
|
|
|||
|
Pдек.к.к 1 |
P(ci ) P (e) t 1 P (e) t . |
|
|||||||||||
|
|
|
i 0 |
|
|
|
|
|
|
|
|
|
||
|
В дискретном симметричном канале без памяти |
|
|
|
|
|||||||||
|
|
t |
|
|
i p |
|
i |
|
|
t |
|
|
||
|
|
|
i |
|
|
n |
i |
i i |
n |
i |
||||
|
P (e) t Cn (m 1) |
|
|
|
|
|
(1 p) |
|
Cn p |
(1 p) |
|
|||
|
|
|
|
|
||||||||||
|
|
i 0 |
t |
|
m 1 |
|
|
n |
|
i 0 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
и |
Pдек.к.к |
1 Cni |
pi (1 p)n i |
Cni |
pi (1 p)n i . |
(45) |
||||||||
|
|
|
i 0 |
|
|
|
|
|
|
i t 1 |
|
|
|
|
Алгоритм полного декодирования. Если таблица декодирования содержит кроме исправляемых ошибочных комбинаций и обнаруживаемые комбинации, то при полном декодировании все обнаруживаемые комбинации также используются для исправления ошибок. При этом декодер исправит также часть комбинаций с большим, чем t , числом ошибок. В этом случае вероятность ошибочного декодирования можно оценить неравенством
n |
|
Pдек.к.к Cni pi (1 p)n i . |
(46) |
i t 1
Режим обнаружение ошибок
Если декодер работает в режиме обнаружения ошибок, то вероятность того, что декодер не обнаружит ошибки (вероятность необнаруженной ошибочной кодовой комбинации)
|
|
|
n |
|
|
|
|
|
|
|
Pн.о.к.к |
ni |
pi (1 p)n i |
, |
|
(47) |
|||
|
|
|
i dmin |
|
|
|
|
|
|
где ni – спектр кода. |
|
|
i |
|
|
|
|
||
|
|
|
и |
|
|||||
Например, спектр кода (5,2) равен n |
|
1, 0, 0, 2,1, 0 |
|
|
|||||
P |
|
2 p3 (1 p)2 |
p4 (1 p) . |
(48) |
|||||
н.о.к.к |
|
|
|
|
|
|
|
|
|
Если спектр кода неизвестен, то оценить сверху вероятность необнаруженной |
|||||||||
ошибочной кодовой комбинации можно неравенством (верхняя граница) |
|
||||||||
|
|
|
n |
|
|
|
|
|
|
|
Pн.о.к.к |
Cni |
pi (1 p)n i . |
|
(49) |
i dmin
132
Вероятность ошибки на бит или вероятность ошибки информационного бита после декодирования кодовой комбинации можно оценить по формуле
|
m / 2 |
n |
t i |
|
|
|
|
pb |
|
Cni |
pi (1 p)n i . |
(50) |
|||
|
|
||||||
|
m 1 i t 1 |
n |
|
|
При малых вероятностях ошибки символа в канале ( p 1 ), наибольший вклад в вероятность ошибки будет вносить первое слагаемое суммы, поэтому
pb dmin Pдек.к.к .
n
Вероятность ошибки на бит pb рассчитывается в предположении, что информации без избыточности или когда энтропия источника H (A) log2 m .
(51)
источник
Границы для минимального расстояния кодов
Границы минимального расстояния используются для доказательства существования и оценки эффективности помехоустойчивых кодов.
Граница Хэмминга. Для любого блочного m-ичного (n, k) кода, исправляющего t ошибочных символов или имеющего dmin 2t 1 , число проверочных символов должно быть равным
|
t |
i |
i |
(52) |
r n k logm |
Cn (m 1) |
. |
||
i 0 |
|
|
|
|
Это условие следует из неравенства |
|
|
|
|
t |
|
|
|
|
mn k Cni (m 1)i . |
|
(53) |
||
i 0 |
|
|
|
|
Если при заданных n , k и t выполняется строгое равенство, то |
код называется |
совершенным кодом. Совершенный код исправляет все t и менее ошибочных символов и не исправляет ни одной комбинации с большим числом ошибочных символов. Например, двоичный ( m 2 ) код Хэмминга (7, 4) , исправляющий одиночные ошибки ( t 1), является совершенным кодом.
Граница Синглтона. Минимальное расстояние по Хэммингу линейного блочного
(n, k) кода удовлетворяет неравенству |
|
|
|
|
|
|
|
|
dmin |
n k 1. |
(54) |
||||||
Если выполняется равенство, то такой код называют кодом с максимальным |
||||||||
расстоянием. Для кода с максимальным расстоянием |
|
|||||||
dmin n k 1 2t 1 . |
(55) |
|||||||
Т.е. для исправления ошибочного символа достаточно двух проверочных символов |
||||||||
(один определяет положение ошибочного символа, а второй значение ошибки). |
|
|||||||
Пример 1: для кода (5,2) dmin 4 . Действительное значение dmin 3 . |
|
|||||||
Пример 2: для кода Хэмминга (7,4) dmin |
4 . Действительное значение dmin |
3 . |
||||||
Примером кода с максимальным расстоянием является код Рида–Соломона. |
||||||||
Граница Плоткина. Минимальное расстояние dmin двоичного (n, k) |
кода должно |
|||||||
удовлетворять неравенству |
|
|
2k 1 |
|
||||
|
|
|
|
|||||
d |
min |
|
|
|
n . |
(56) |
||
2k |
|
|||||||
|
|
1 |
|
|||||
Пример 1: для кода (5,2) dmin 10 / 3 3,333 . Действительное значение dmin |
3 . |
|||||||
Пример 2: для кода Хэмминга |
(7,4) |
dmin |
56 |
3, 733 . Действительное значение |
||||
|
||||||||
|
|
|
|
15 |
|
|
dmin 3 .
133
Граница Плоткина более точная для низкоскоростных кодов, когда скорость кода Rc k / n мала. Границы Синглтона и Плоткина грубые, но вычисляются проще, чем граница Хэмминга.
134
ЛЕКЦИЯ 17
Линейные систематические коды. Код с проверкой на чётность. Коды Хэмминга. Порождающая и проверочная матрицы. Алгоритмы кодирования и декодирования. Их реализация на примере кода (7,4).
Простые двоичные линейные блочные коды
1. Примитивный код. Примитивное кодирование используется для согласования алфавитов источника и канала. Например, для передачи текста по каналу связи посредством сигналов двухпозиционной модуляции, каждую букву на передаче необходимо представить в виде последовательности двоичных символов.
Параметры примитивного кода: (n, k) (n, n) , Rc 1, dmin 1, t qo 0 , спектр кода ni Cni , i 0,1,..., n . Код не способен обнаруживать и исправлять ошибки.
Вероятность ошибки декодирования кодовой комбинации, вероятность необнаруженной ошибочной кодовой комбинации и вероятность ошибки на бит равны
|
|
n |
n |
|
Pдек.к.к Pн.о.к.к |
|
ni |
pi (1 p)n i Cni pi (1 p)n i 1 (1 p)n , |
(57) |
|
|
i dmin |
i 1 |
|
pb p .
Если вероятность ошибки символа в канале p 1 , то
Pдек.к.к Pн.о.к.к n p . |
(58) |
2.Код с проверкой на чётность: (n, k) (n, n 1) (k 1, k ) . Кодовая комбинация кода
спроверкой на чётность получается путём добавления к k информационным символам одного проверочного символа, равного сумме по модулю 2 всех информационных символов:
c (b0 ,b1 ,..., bk 1, k )T , где k b0 b1 ... bk 1 .
Код имеет следующие параметры: |
R |
n 1 |
, |
|
1 |
, d |
|
2 , |
t (d |
|
1) / 2 0 , |
||
|
|
min |
min |
||||||||||
|
|
c |
n |
|
n |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
||||
qo dmin 1 1, код с максимальным расстоянием (т.к. dmin |
n k 1). |
|
|
|
|||||||||
Спектр кода: n 0 при i –нечётное, n |
Ci |
при i –чётное: |
|
|
|
|
|
||||||
i |
i |
n |
|
|
|
|
|
|
|
|
|
|
ni 1, 0,Cn2 , 0,Cn4 ,..., Cn4 , 0,Cn2 , 0,1 .
Порождающая и проверочная матрицы кода равны:
|
|
|
|
|
1 |
0 |
|
.. 0 |
|
|
|
|
|
|
1 |
|||||
|
|
Ik |
|
|
0 |
1 |
|
.. 0 |
|
|
Γ |
T |
|
|
1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
G |
|
Γ |
|
.. |
|
.. .. .. |
, H |
In |
k |
|
|
1 . |
||||||||
|
|
|
|
|
0 |
|
0 |
|
.. |
|
1 |
|
|
|
|
|
|
.. |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
1 |
|
.. 1 |
|
|
|
|
|
|
1 |
Поскольку исправляющая способность кода t 0 , то этот код используют только для обнаружения ошибок. Поэтому
|
n |
|
|
|
n |
|
|
|
|
|
|
|
1 (1 2 p)n |
|
|
|
Pн.о.к.к |
ni pi (1 p)n i |
Cni |
pi (1 p)n i |
или Pн.о.к.к |
|
|
(1 p)n . |
(59) |
||||||||
2 |
||||||||||||||||
|
i dmin |
|
|
i 0, |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
i чётн |
|
|
|
|
|
|
|
|
|
|
||
Если вероятность ошибки символа в канале p 1 , то, отбросив слагаемые при i 2 , |
||||||||||||||||
получим приближённую формулу |
|
|
|
1 |
|
|
|
|
|
|
||||||
|
|
|
|
P |
C 2 p2 |
|
n(n 1) p2 , |
|
|
|
(60) |
|||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
н.о.к.к |
|
n |
2 |
|
|
|
|
|
|
||
|
|
|
dmin |
|
|
|
|
|
|
|
|
|
||||
|
p |
|
P |
|
(n 1) p2 |
(при переспросе). |
|
(61) |
||||||||
|
|
|
|
|||||||||||||
|
b |
|
n |
|
н.о.к.к |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
135
|
3. Код с повторением: |
(n, k) (n,1) . Кодовая комбинация кода получается путём n |
||||||||||||||||||||||||||||||||||||||||||||||
кратного повторения информационного символа: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
c (b , b ,..., b )T . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Код |
имеет |
следующие |
параметры: |
|
|
|
R |
1 |
, |
|
|
, |
|
d |
|
|
n , |
t (n 1) / 2 , |
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
min |
|||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
|
|
|
n |
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
qo |
dmin 1 n 1, код с максимальным расстоянием (т.к. dmin |
n k 1). |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
Если |
n – нечётное, |
|
то |
код |
с повторением |
|
является совершенным |
кодом, |
т.е. |
||||||||||||||||||||||||||||||||||||||
t |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cni 2n k 2n 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
i 0 |
|
|
n 1,0 0, 0,..., 0,11 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Спектр кода: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Этот код можно использовать для обнаружения и исправления ошибок: |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pдек.к.к 1 Cni pi (1 p)n i |
, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(62) |
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
Pн.о.к.к |
ni pi (1 p)n i |
pn . |
|
|
|
|
|
|
|
|
|
|
|
|
(63) |
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
i dmin |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
4. Код Хэмминга: |
(n, k) (2r |
1, 2r |
1 r) , |
|
|
r |
– число |
проверочных |
|
символов |
кода. |
||||||||||||||||||||||||||||||||||||
Кодовая комбинация кода состоит из k информационных и r |
проверочных символов: |
|
||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
c (b ,b ,..., b |
, |
k |
, |
k 1 |
,..., |
k r 1 |
)T . |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
0 1 |
|
|
|
|
|
|
k 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
k 2r 1 r |
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
Код имеет следующие параметры: R |
|
k |
|
|
2r 1 r |
, 1 |
k |
|
|
r |
|
, |
d |
|
3 , t |
1 и |
|||||||||||||||||||||||||||||||
|
|
n |
|
|
|
|
2r |
|
1 |
|
n |
2r 1 |
|
|||||||||||||||||||||||||||||||||||
qo |
dmin 1 2 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
min |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Код Хэмминга – совершенный код, т.к. Cni |
|
2n k |
1 n . |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
|
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Pдек.к.к 1 Cni pi (1 p)n i 1 (1 p)n n p (1 p)n 1 , |
|
|
|
|
|
|
|
(64) |
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
i 0 |
p |
p p (1 p)n 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(65) |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Пример: код Хэмминга (7,4), r 3 , R |
4 |
, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
1 0 0 0 |
|
|
|
|
|
|
|
|
|
|
1 0 1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
0 1 0 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 1 1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
Ik |
|
0 0 1 0 |
|
|
|
|
|
|
|
Γ |
T |
|
1 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
G |
0 0 0 1 |
, H |
|
0 1 1 . |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
Γ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
1 1 1 0 |
|
|
|
|
|
|
|
|
|
n k |
|
1 0 0 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
0 1 1 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
1 1 0 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
136
Кодовые комбинации кода Хэмминга (7,4), их вес, векторы ошибок и синдромы
b |
c |
(c) |
|
eT |
sT |
0000 |
0000000 |
0 |
|
0000000 |
000 |
0001 |
0001011 |
3 |
|
1000000 |
101 |
0010 |
0010110 |
3 |
|
0100000 |
111 |
0011 |
0011101 |
4 |
|
0010000 |
110 |
0100 |
0100111 |
4 |
|
0001000 |
011 |
0101 |
0101100 |
3 |
|
0000100 |
100 |
0110 |
0110001 |
3 |
|
0000010 |
010 |
0111 |
0111010 |
4 |
|
0000001 |
001 |
1000 |
1000101 |
3 |
|
|
|
1001 |
1001110 |
4 |
|
|
|
1010 |
1010011 |
4 |
|
|
|
1011 |
1011000 |
3 |
|
|
|
1100 |
1100010 |
3 |
|
|
|
1101 |
1101001 |
4 |
|
|
|
1110 |
1110100 |
4 |
|
|
|
1111 |
1111111 |
7 |
|
|
|
Спектр кода: {ni } 1, 0, 0, 7, 7, 0, 0,1 .
При малой вероятности ошибки символа в канале ( p 1 )
Pдек.к.к 21p2 ,
n
Pн.о.к.к ni pi (1 p)n i 7 p3 ,
i dmin
pb 9 p2 .
По сравнению с примитивным кодом, для которого pb p , у кода Хэмминга вероятность ошибки на бит убывает по квадратичному закону.
137
ЛЕКЦИЯ 18
Другие виды помехоустойчивых кодов. Циклические коды. Итеративные и каскадные коды. Особенности кодирования и декодирования в каналах с памятью. Свёрточные коды. Понятие о декодировании с "мягким" решением.
Циклические коды
Циклические коды представляют собой подкласс линейных блочных кодов. Кодирование и декодирование циклических кодов реализуется с помощью регистров сдвига.
Основной особенностью циклических кодов является то, что циклический сдвиг
кодовой |
комбинации |
снова |
даёт кодовую |
комбинацию. |
Например, |
если |
|||||||||||||
c (c , c , c ,..., c |
n 2 |
, c |
)T – кодовая |
комбинация |
циклического |
кода, |
то |
||||||||||||
0 |
1 |
2 |
|
n 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
c (c |
, c , c ,..., c |
|
|
, c |
|
)T |
– другая кодовая комбинация циклического кода. |
|
|||||||||||
n 1 |
|
0 1 |
|
n 3 |
n 2 |
|
|
|
|
|
|
|
|
|
|
|
|||
Кодовые комбинации циклического (n, k) |
кода можно рассматривать как многочлены |
||||||||||||||||||
или полиномы, |
|
которые ограничены по модулю многочлена |
xn 1. Коэффициенты этих |
||||||||||||||||
многочленов соответствуют символам кодовой комбинации: |
|
|
|
||||||||||||||||
|
|
c(x) c |
0 |
c x ... c |
n 1 |
xn 1 mod(xn 1) c |
n 1 |
xn 1 |
... c x c mod(xn 1) . |
|
|||||||||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
0 |
|
|
|||
или |
|
|
|
|
|
|
|
|
|
|
|
c(x) c(x) mod(xn 1) . |
|
|
(66) |
||||
Запись a(x) mod b(x) означает остаток от деления a(x) на b(x) . |
|
|
|||||||||||||||||
Например, |
|
|
|
если |
|
коэффициентами |
являются |
двоичные |
символы, |
то |
|||||||||
(x3 x 1) mod(x 1) 1 . |
|
|
|
|
|
|
|
|
|
|
Взятие остатка от деления на xn 1 задаёт свойство циклического сдвига. Циклический сдвиг на i позиций в полиномиальном представлении соответствует умножению многочлена
на xi и взятию остатка от деления полученного многочлена на xn |
1: |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
c(x)x |
q(x) |
c1 (x) |
, |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
xn 1 |
|
xn 1 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
c (x) c(x)x q(x)(xn 1) , |
|
|
|
|
|
|
|
||||||
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
где q(x) |
– частное, c1(x) |
– остаток. |
|
|
|
|
|
|
|
|
|
|
|
|
||||
Например, умножение на x или циклический сдвиг на одну позицию даёт многочлен |
||||||||||||||||||
|
c (x) c(x)x mod(xn 1) c |
xn c |
xn 1 ... c x2 |
c x mod(xn 1) |
|
|
|
|||||||||||
|
1 |
|
|
|
|
n 1 |
|
n 2 |
1 |
|
0 |
|
|
|
|
|
||
c |
(xn 1) c |
c |
|
xn 1 |
... c x2 |
c x mod(xn 1) c |
|
xn 1 ... c x2 |
c x c |
n 1 |
. |
|
||||||
n 1 |
n 1 |
n 2 |
|
1 |
0 |
|
|
n 2 |
|
1 |
0 |
|
|
|||||
Порождающий многочлен циклического кода |
|
|
|
|
|
|
|
|||||||||||
Порождающий многочлен циклического (n, k) кода |
|
g(x) |
– это многочлен степени |
|||||||||||||||
n k , который делит без остатка xn 1: |
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
(xn 1) mod g(x) 0 . |
|
|
|
|
|
|
(67) |
|||||
Любой многочлен |
c(x) |
является кодовым многочленом циклического кода, |
если он |
|||||||||||||||
делится без остатка на порождающий многочлен g(x) : c(x) mod g(x) 0 . |
|
|
|
|
||||||||||||||
Кодирование циклическим кодом |
|
|
|
|
|
|
|
|
|
|
||||||||
Несистематическое кодирование |
|
|
|
|
|
|
|
|
|
|
||||||||
Кодирование циклическим (n, k) кодом многочлена |
b(x) |
степени |
|
k 1 в |
||||||||||||||
несистематической форме описывается выражением |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
c(x) b(x)g(x) mod(xn 1) , |
|
|
|
|
|
|
(68) |
||||||
где g(x) |
– порождающий многочлен кода. |
|
|
|
|
|
|
|
|
|
|
При несистематическом кодировании информационный многочлен в явном виде не содержится в кодовом многочлене.
138
Систематическое кодирование
Систематическое кодирование можно осуществить, если сдвинуть информационные символы в сторону увеличения степеней на n k позиций и к полученному многочлену прибавить многочлен проверочных символов:
c(x) b( x)xn k r(x) mod(xn 1) , |
(69) |
где r(x) b( x)xn k mod g(x) – многочлен проверочных символов циклического кода.
При систематическом кодировании k старших коэффициентов кодового многочлена являются информационными символами.
Можно убедиться, что c(x) mod g(x) 0 .
Передача кодового многочлена по дискретному каналу с ошибками
При передаче кодового многочлена c(x) по дискретному каналу с ошибками, на выходе канала будет получен многочлен равный
|
|
|
y(x) c(x) e(x) , |
(70) |
где e(x) e |
e x ... e |
xn 1 – многочлен ошибок, e |
– значения ошибок. |
|
0 |
1 |
n 1 |
i |
|
Синдромный многочлен
Синдромный многочлен s(x) , который используется при обнаружении и исправлении
ошибок в кодовой комбинации циклического кода, находится по формуле |
|
s(x) y(x) mod g(x) , |
(71) |
где y(x) c(x) e(x) – принятый кодовый многочлен с ошибками. |
|
Свойство синдромного многочлена: |
|
s(x) y(x) mod g(x) (c(x) e(x)) mod g(x) e(x) mod g(x) . |
(72) |
Если при передаче кодовой комбинации ошибок в канале не было, т.е. |
e(x) 0 , то |
s(x) 0 . При возникновении ошибок s(x) 0 . |
|
Реализация операций умножения, деления и взятия остатка на основе регистра сдвига
По аналогии с z преобразованием, для определения текущего коэффициента результата можно использовать следующие правила:
1)c(x) ck ,
2)c(x)x ck 1 ,
|
|
|
|
|
|
n |
|
|
3) c(x) a(x)b(x) ck |
bi ak i – дискретная свёртка. |
|
||||||
|
|
|
|
|
|
i 0 |
|
|
Умножение многочленов |
c(x) a(x)b(x) , |
(73) |
||||||
|
|
|
|
|
|
|
||
где |
|
|
|
|
|
|
|
|
a(x) a |
a x a |
x2 ... a xm |
– входной многочлен, |
|
||||
0 |
1 |
2 |
|
|
m |
|
|
|
b(x) b |
b x b x2 |
... b xn |
– множитель, |
|
||||
0 |
1 |
2 |
|
|
n |
|
|
|
c(x) c |
c x c x2 |
... c |
m n |
xm n |
– произведение. |
|
||
0 |
1 |
2 |
|
|
|
|
|
|
Степень многочлена deg( f (x)) – это наибольшая степень независимой переменной, |
||||||||
при которой коэффициент не равен нулю. |
|
|||||||
При умножении многочленов deg(c(x)) deg(a(x)) deg(b(x)) . |
|
|||||||
Если deg(a(x)) m , |
deg(b(x)) n , то deg(c(x)) deg(a(x)) deg(b(x)) m n . |
|
Умножения многочленов реализуется с помощью алгоритма умножения столбиком:
139