Лекция №5

Пример: построить систематический код с разрядностью 10 для исправления однократной ошибки: n=10, a =1, k -? r -?

d_min>= 2*a+1 – минимальное кодовое расстояние

d_min>=3

r=n-k>=log₂(ΣC_n^t)= log₂(C₁₀⁰+C₁₀¹)= log₂(1+10!/1*9!) = log₂(1+10)= log₂11=3.4

r>=4

n-r=k, k=10-4=6 (n;k); (10,6)

Избыточность кода: W=r/n=(n-k)/n=(10-6)/10=0.4

Скорость кодирования: V=k/n=6/10=0.6(бит/с)

D_{k * (n-k)} = D_6*4

d_min-1=3-1=2 единицы в каждой строке

Систематический код невозможно реализовать, если нельзя построить матрицу D и если величина а>k, в нашем примере а=1 k=6, а<k, следовательно код возможно реализовать.

D_6*4 = 1| 0011

2| 0101

3| 0110

4| 1001

5| 1010

6| 1111

Проверяем, сумма по модулю двух любых строк должна содержать d_min-2 и более «единиц»:

D(D1,D2)=0110

D(D1,D3)=0101

D(D1,D4)=1010

D(D1,D5)=1001

D(D1,D6)=1100

D(D2,D3)=0011

D(D2,D4)=1100

D(D2,D5)=1111

D(D2,D6)=1010

D(D3,D4)=1111

D(D3,D5)=1100

D(D3,D6)=1001

D(D4,D5)=0011

D(D4,D6)=0110

D(D5,D6)=0101

A=[I_k*k] [D_k*(n-k)]=[I_6*6] [D_6*4]

A=100000 0011

010000 0101

001000 0110

000100 1001

000010 1010

000001 1111

H=[D^T] [I_(n-k)*(n-k)] =[D^T] [I_4*4]

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10

H= 0 0 0 1 1 1 1 0 0 0

0 1 1 0 0 1 0 1 0 0

1 0 1 0 1 1 0 0 1 0

1 1 0 1 0 1 0 0 0 1

Количество уравнений 4, т.к. в проверочной матрице 4 строки:

r1=a4 a5 a6 a7

r2=a2 a3 a6 a8

r3=a1 a3 a5 a6 a9

r4=a1 a2 a4 a6 a10

Проверочные разряды:

a7=a4 a5 a6

a8=a2 a3 a6

a9=a1 a3 a5 a6

a10=a1 a2 a4 a6

А – передаваемая информационная последовательность

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10

1 0 0 1 0 0 1 0 1 0

a7=1 0 0=1

a8=0 0 0=0

a9=1 0 0 0=1

a10=1 0 1 0=0

r1=1 0 0 1=0

r2=0 0 0 0=0

r3=1 0 0 0 1=0

r4=1 0 1 0 0=0

В – полученная информационная последовательность

b1 b2 b3 b4 b5 b6 b7 b8 b9 b10

1 0 0 1 0 1 1 0 1 0

r1=1 0 1 1=1

r2=0 0 1 0=1

r3=1 0 0 1 1=1

r4=1 0 1 1 0=1

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

A=100000 0011

010000 0101

001000 0110

000100 1001

000010 1010

000001 1111 – ошибка в 6-м разряде

Необходимо инвертировать шестой разряд:

В=100101 1010

e= 000001 0000 – исправляющий вектор

B e=100100 1010

Тест 2. В – полученная информационная последовательность

b1 b2 b3 b4 b5 b6 b7 b8 b9 b10

1 0 0 1 11 1 0 1 0

r1=1 1 1 1=0

r2=0 0 1 0=1

r3=1 0 1 1 1=0

r4=1 0 1 1 0=1

R = 0101

Ищем опознаватель.

A=100000 0011

010000 0101 – ошибка во втором разряде?

001000 0110

000100 1001

000010 1010

000001 1111

Вывод:Ошибка обнаружена, но локализована неверно. Исправление будет некорректным.

В=100111 1010

e= 010000 0000 – исправляющий вектор

B e=1 1 01 11 1010

Систематический код Хэмминга

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

d_min=3

r>=log₂ n

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

при первой проверке получалась цифра с весом младшего разряда - 2⁰;

при 2-ой проверке цифра с весом 1-го разряда - 2¹;

и т.д.

2⁰,2¹,…,2^n-1. Тогда сумма всех проверок даст номер ошибочного разряда.