Преобразование Windows-кодирования в систематические коды

Пример: построить систематический код с исправлением одиночных искажений S=1, с числом информационных элементов k=8.

1.Определение минимального кодового расстояния систематического d_min=2s+1=2·1+1=3.

2.Определение общего количества элементов систематического кода

N_p£ 256£ , откуда n=13.

3.Определение числа проверочных элементов систематического кода r=n-k=13-8=5.

4.Из полного множества кодовых комбинаций, состоящих из 5 элементных кодов, выбираются 8 кодовых комбинаций, вес каждой из которых p³d_min-1.

3 - 1 = 2 (00011, 00101, 00110, 01001, 01010, 01100, 11000).

5.Построение производящей матрицы систематического кода G .

100000000 00011
010000000 00101
= 001000000 00110
000100000 01001
000010000 01010
00000100 011000
00000010 100100
00000001 110000

6.Определение r проверочных элементов по известным информационным элементам.

6.1.Построение проверочной матрицы H

Для построения проверочной матрицы H необходимо построить подматрицу D

D = 00011101

a1a2a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5

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

0 0 0 1 1 1 0 1 0 1 0 0 0

0 1 1 0 0 1 0 1 0 0 1 0 0

1 0 1 0 1 0 1 0 0 0 0 1 0

1 1 0 1 0 0 0 0 0 0 0 0 1

По полученной проверочной матрице H определяются проверочные элементы b , b , b , b , b

b =a Å a

b =a Å a Å a Å a

b =a Å a Å a Å a (33)

b =a Å a Å a Å a

b =a Å a Å a

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

Например: буква Т русского алфавита в системе Windows -кодирования имеет вид

a a a a a a a a a₁a₂a₃a₄a₅a₆a₇a₈b₁b₂b₃b₄b₅

Т ®1 1 0 1 0 0 1 0 ® 1 1 0 1 0 0 1 0 1 1 1 0 1

b₁=1Å 0=1

b₂=1Å 0 Å 0 Å 0=1

b₃=1Å 0 Å 0 Å 0=1

b₄=1Å 0 Å 0 Å 1=0

b₅=1 Å 1 Å 1=1

В этом случае общий вид систематического кода при преобразовании семантического элемента Windows -кодирования имеет вид

N_i=a₁a₂a₃a₄a₅a₆a₇a₈b₁b₂b₃b₄b₅ (34)

Преобразуя по полученным формулам (33, 34) исходные в системе Windows -кодирования двоичные кодовые комбинации семантического алфавита, получим полное множество его отображений в систематических кодах, обнаруживающих и исправляющих возникающие при их передаче по каналам связи искажения.

При декодировании принятых кодовых комбинаций систематического кода Windows -кодирования алгоритм распознавания искажений кодовых комбинаций определяется следующими уравнениями:

b =b₁ Å a₇ Å a₈

b =b₂ Å a₄ Å a₅ Å a₆ Å a₈

b =b₃ Å a₂ Å a₃ Å a₆ Å a₈ (35)

b =b₄ Å a₁ Å a₃ Å a₅ Å a₇

b =b₅ Å a₁ Å a₂ Å a₄

Например при передаче Windows -кода буквы Т =11010 0 101110 произошло искажение, и принята комбинация Т= 11010 1 1011101 (искажение в 6-ом разряде, передан 0 принята 1).

Определяем проверочные символы b ... b (в рассматриваемом примере a₁=1,a₂=1, a₃=0, a₄=1, a₅=0, a₆=1, a₇=1, a₈=0, b₁=1, b₂=1, b₃=1, b₄=0, b₅=1).

b =1 Å 1 Å 0=0

b =1 Å 1 Å 0 Å 1 Å 0=1

b =1 Å 1 Å 0 Å 1 Å 0=1

b =0 Å 1 Å 0 Å 0 Å 1=0

b =1 Å 1 Å 1 Å 1=0

Равенство уравнений b и b единице указывает, что при приеме произошло искажение. Искаженным может быть один из элементов b₂, b₃, a₂, a₃, a₄, a₅, a₆, a₈, но элементы a₂, a₃, a₄, a₅, a₈ входят в уравнения b , b , b и искаженными быть не могут. Остается распознать элементы b₂, b₃, a₆.

Элемент a₆ входит в оба уравнения, содержащих искаженный элемент (b и b ), следовательно, он и искажен. Заменяя в элементе a₆ значение 1 на 0, получим исправленную кодовую комбинацию Т = 11010 0 1011101.