- •Теория информационных процессов и систем
- •Лекции читает канд.техн.наук, доцент Литвинов Владислав Леонидович
- •Связь между корректирующей способностью кода и длиной кода
- ••Пусть необходимо исправить ошибки кратности от 1 до t. Число возможных однократных ошибок
- •• Отсюда получим:
- ••В частном случае, когда требуется исправить однократные ошибки, имеем зависимость 2r – r
- ••Сравните с аналогичной таблицей для помехоустойчивого кода, исправляющего двукратные ошибки
- •Систематические коды
- ••Получение кодовых комбинаций производится с помощью порождающих матриц, состоящих из k строк и
- ••Информационную подматрицу часто берут в виде квадратной единичной матрицы:
- •• Пусть, например, порождающая матрица (7,4)-кода имеет вид:
- •Обнаружение ошибок с помощью систематических кодов
- •• Получается матрица H PT Ir ,
- ••Возьмем порождающую матрицу (7.4)-кода из предыдущего примера и составим проверочную матрицу. Проверочная подматрица
- ••Проверим полученное в предыдущем примере кодовое слово
- ••Синдром ненулевой, следовательно, обнаружена ошибка. Можно ли эту ошибку не только обнаружить, но
- •Коды Хемминга
- ••Затем строят порождающую матрицу G, исходя из того, что матрицы H и G
Теория информационных процессов и систем
Кафедра информационных управляющих систем
Лекции читает канд.техн.наук, доцент Литвинов Владислав Леонидович
Связь между корректирующей способностью кода и длиной кода
• Обычная последовательность выбора кода следующая:
1.исходя из мощности M первичного алфавита, определяется количество информационных разрядов;
2.задается возможная кратность ошибок, подлежащих обнаружению и исправлению;
3.определяется количество дополнительных проверочных разрядов, которые вместе с информационными определят длину кода n.
•Пусть известна мощность первичного алфавита М.
•Необходимое количество информационных битов k ≥ log2M.
•Пусть необходимо исправить ошибки кратности от 1 до t. Число возможных однократных ошибок в коде длиной n равно
•C1n n ,
• |
число двукратных ошибок равно Cn2 n(n 1) / 2 , число возможных t- |
|||
|
кратных ошибок равно Cnt |
n! |
|
. |
|
|
t!(n |
t)! |
|
• |
t |
|
|
|
Общее число ошибок E Cni . |
|
|
i1
•Эти Е ошибок могут проявиться в каждой из 2k возможных входных
последовательностей. Полное число ошибочных комбинаций, подлежащих исправлению, равно Е∙2k. Код длиной n обеспечивает исправление не более 2n - 2k комбинаций, так как именно столько запрещенных комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде
•Е∙2k ≤ 2n - 2k
• Отсюда получим:
2n 1 E
2k
•Обозначив буквой r число проверочных символов, и учитывая, что r = n – k, получим:
|
t |
|
|
|
2r 1 Cni |
|
|
|
i 1 |
t |
|
• |
Учитывая, что 1 Сn0 |
||
, можно записать 2r Cni или |
|||
|
|
i 0 |
|
|
t |
|
|
|
r log2 Cni |
|
|
|
i 0 |
|
|
• |
Это так называемая граница Р.Хемминга (или условие Хемминга), |
||
|
связывает число проверочных бит и значность кода. |
• Richard Wesley Hamming (1915–1998) was a mathematician whose work had many implications for computer science and telecommunications. His contributions include the Hamming code (which makes use of a Hamming matrix), the Hamming window (described in section 5.8 of his book Digital Filters), Hamming numbers, Sphere-packing (or hamming bound) and the Hamming distance.
•В частном случае, когда требуется исправить однократные ошибки, имеем зависимость 2r – r – 1 ≥ k.
•Оценить количество проверочных символов и избыточность кода можно из таблицы, построенной по указанной зависимости:
r |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
|
|
|
k |
1 |
4 |
11 |
26 |
57 |
120 |
247 |
502 |
1013 |
|
|
|
|
|
|
|
|
|
|
F |
0,67 |
0,43 |
0,27 |
0,16 |
0,10 |
0,06 |
0,03 |
0,02 |
0,01 |
|
|
|
|
|
|
|
|
|
|
F n k n
•Вспомним вторую теорему Шеннона. Действительно, теоретически, увеличивая длину блока можно бесконечно уменьшать избыточность, обеспечивая вместе с тем помехоустойчивость кода.
•Сравните с аналогичной таблицей для помехоустойчивого кода, исправляющего двукратные ошибки
•Сравните с аналогичной таблицей для помехоустойчивого кода, исправляющего двукратные ошибки
r |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
1 |
1 |
2 |
3 |
5 |
9 |
15 |
23 |
35 |
53 |
79 |
115 |
|
|
|
|
|
|
|
|
|
|
|
|
|
F |
0,67 |
0,75 |
0,67 |
0,63 |
0,55 |
0,44 |
0,35 |
0,28 |
0,22 |
0,17 |
0,13 |
0,10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
•Выполняется ли неравенство Хемминга в задаче о разведчиках??
•Ответ: да, но только с учетом 2-кратных ошибок. Если же требуется исправлять и однократные ошибки, то
•r≥log2(1+8+28)=6
Систематические коды
•Систематические коды относятся к группе блочных разделимых кодов. Для систематического кода сумма по модулю 2 двух разрешенных комбинаций также дает разрешенную комбинацию (свойство замкнутости). Все разрешенные комбинации систематического
•(n, k)-кода можно получить, располагая k-значными исходными комбинациями. При этом:
1.в число исходных комбинаций не должна входить тривиальная (нулевая);
2.все исходные комбинации должны быть линейно независимы, т.е. ни одна из них не может быть получена путем суммирования других;
3.для обеспечения требуемой корректирующей способности
минимальное кодовое расстояние dmin исходных комбинаций должно удовлетворять условиям Хемминга.
•Получение кодовых комбинаций производится с помощью порождающих матриц, состоящих из k строк и n столбцов:
a11 |
a12 |
... |
a1k |
b11 |
b12 |
... |
b1r |
|
||||||
G a |
21 |
a |
22 |
... |
a |
2k |
b |
21 |
b |
22 |
... |
b |
2r |
|
|
a |
... |
a |
b |
b |
... |
b |
|
||||||
a |
k1 |
k 2 |
kk |
k1 |
k 2 |
|
|
|||||||
|
|
|
|
|
|
|
|
kr |
•В классической (канонической) форме кода элементы первых k столбцов служат для информационных целей, а оставшихся – для проверочных. Соответственно, порождающую матрицу G можно
представить в виде двух подматриц – информационной Ik и проверочной P.
• G Ik |
|
P |
, где |
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
a11 |
a12 |
... |
a1k |
|
b11 |
b12 |
... |
b1r |
|
|||||||
I |
k |
a |
21 |
a |
22 |
... |
a |
2k |
|
P b |
21 |
b |
22 |
... |
b |
2r |
|
||
|
|
|
a |
... |
a |
|
|
b |
... |
b |
|
||||||||
|
|
|
a |
k1 |
k 2 |
kk |
|
b |
k1 |
k 2 |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
kr |
•Информационную подматрицу часто берут в виде квадратной единичной матрицы:
|
|
|
1 |
0 |
... |
0 |
|
I |
|
|
0 |
1 |
... |
0 |
|
k |
|
|
|||||
|
|
0 |
0 |
... |
|
||
|
|
|
1 |
||||
|
|
|
|
|
|
|
|
•При этом проверочная подматрица P должна строиться с соблюдением следующих условий:
1.вес (количество единиц) каждой строки подматрицы должен быть не менее dmin-1;
2.все строки должны быть различны;
3.кодовое расстояние между любыми двумя строками подматрицы должно быть не менее dmin-2.