ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ

#1 Постановка задачи кодирования

В теории передачи информации чрезвычайно важными являются проблемы кодирования и декодирования, обеспечивающие надежную передачу информации по каналу «с шумом». Передача информации сводится к передаче по некоторому каналу символов некоторого алфавита. Однако в реальных ситуациях сигналы при передаче практически всегда могут искажаться, и переданный символ воспринимается неправильно.

Например, в системе ЭВМ-ЭВМ одна из машин может быть связана с другой через спутник. Канал связи в этом случае реализуется электромагнитным полем между поверхностью земли и спутником. Электромагнитные сигналы, накладываясь на внешнее поле, могут исказиться и ослабиться. Для обеспечения надежности передачи информации в таких системах разработаны эффективные методы, использующие вводу различных типов.

О₁ Двоичнымназовем алфавит, состоящий из 0 и 1. Тогда сообщение есть конечная последовательность символов этого алфавита.

О₂ Код (кодовое слово) – последовательность символов в алфавите 0,1, которая получена из подлежащего передаче сообщения с помощью кодирования по определенной схеме.

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

Блочный двоичный (m,n) код определяется двумя формулами.

E: {0;1}^m –> {0;1}ⁿ

D: {0;1}ⁿ –> {0;1}^m,

где m≤n и {0;1}ⁿ множество всех последовательностей длины n. Функция E определяет схему кодирования, а D – схему декодирования.

Математическую модель системы связи можно представить в виде схемы:

сообщение –>(E)модель канала связи –>(T)принятое сообщение–>(D)декодированное сообщение

T – функция ошибок, E и D выбирается так, чтобы композиция D○T○E была функцией, близкой к тождественной.

Двоичный (m,n) код содержит 2^m слов.

Коды делятся на 2 больших класса:

1) Коды с обнаружением ошибок, которые с большей вероятностью определяют наличие ошибки в принятом сообщении

2) Коды с исправлением ошибок, могут с большей вероятностью восстановить принятое сообщение.

П₁ (код с проверкой четности). Это пример кода класса 1.

Пусть a=a₁…a_m, схема кодирования Е(а)=b_i…b_m+1, где b_i=a; при i=1…m.

0, _i – четное число

b_m+1=

1, _i – нечетное число

D(b)=c=c_1,…,c_m. c_i=b_i, i=1,…,m

При m=2 E(00) = 000 *для 3 и 4

E(01) = 011

E(10) = 101

E(11) = 110

При m=3 E(000) = 0000. E(001)=0011. E(010)=0101. E(011)=0110. E(100)=1001. E(101)=1010. E(110)=1100. E(111)=1111.

При m=4. E(0000)=00000. E(0001)=00011. E(0010)=00101. E(0011)=00110. E(0100)=01001. E(0101)=01010. E(0110)=01100. E(0111)=01111. E(1000)=10001. E(1001)=10010. E(1010)=10100. E(1011)=10111. E(1100)=11000. E(1101)=11011. E(1110)=11101. E(1111)=11111.

Очевидно, что под разрядная сумма любой кодированной последовательности от 1 до m+1 ( _i) т.е. b₁+…+b_m+1=0 (mod 2), т.е. если _i – нечетна, то при передаче сообщения произошла ошибка, однако если _i четная, то еще не означает, что ошибки не было. Подразрядная сумма окажется четной при любом четном числе ошибок.

П₂ (код с тройным повторением). Это пример весьма неэкономичного кода с исправлением ошибок.

Схема кодирования (функция E) определяется таким образом: каждое сообщение разбивается на блоки длины m и каждый блок передается трижды. Схема декодирования (D) определяется так: полученное сообщение разбивается на блоки 3m, и в каждом блоке из 3 символов b; b_i+m; b_i+2m, принимающих значение 0 или 1 выбирается тот, который встретился большее число раз (2 или 3 раза). Этот символ считается i-ым символом в расшифрованном сообщении.

#2 Расстояние Хемминга

О₁ На множестве двоичных слов длины m расстоянием d(a;b) называется число несовпадающих позиций этих слов.

П₁ a=01101

b=00111

d(a;b) = 2. Это расстояние Хемминга. Оно удовлетворяет следующим аксиомам расстояний

1) d(a;b) ≥ 0 или d(a;b)=0 когда a=b

2) d(a;b) = d(b;a)

3) d(a;b) + d(b;c) ≥ ≥ d(a;c) – неравенство треугольника

Весом (w(a)) слова a называют число единиц среди его координат. Тогда d(a;b) есть вес их суммы. d(a;b) = w (a “ координатное сложение по модулю 2” b).

П₂ a+b=01101

01010 w(a)=3

Интуитивно понятно, что код тем лучше приспособлен к обслуживанию и исправлению ошибок, чем больше различаются кодовые слова. Расстояние Хемминга позволяет это уточнить.

Т₁ Для того чтобы код позволял обнаруживать ошибки в k или менее позициях необходимо и достаточно чтобы наименьшее расстояние между кодовыми словами было ≤ k+1.

Т₂ Для того чтобы он позволял исправлять все ошибки в k или менее позициях необходимо и достаточно, чтобы наименьшее расстояние между кодовыми словами было ≤ 2k+1.

В математической модели кодирования и декодирования удобно рассматривать строки ошибок. Данное сообщение А кодируется кодовым словом b= При передаче канал связи добавляет к нему строку ошибок l=l_1….l_n, что приемник принимает сигнал c=c₁…c_n, c_i=b_i+l_i. Система, исправляющая ошибки переводит слово с₁, b₁ в ближайшее слово a_n, b_т. Система обнаруживающая ошибки только устанавливает является ли принятое слово кодовым или нет. Последнее означает, что при передаче произошла ошибка.

П₁ Рассмотрим (2,3) код с проверкой четности. 000,011,110,101. Минимальное расстояние между кодовыми словами равно двум. Этот код способен обнаруживать однократную ошибку. Рассмотрим (2,5) код со схемой кодирования (неважно как она сделана). Е(0,0)=00000=b¹; E(01)=01011=b²; E(10)=10101=b³; E(11)=11110=b⁴.

Минимальное расстояние между кодовыми словами равно 3. Этот код способен исправлять однократную ошибку. Однократная ошибка приводит к приему слова, находящегося на расстоянии единица от единственного кодового слова, которое и было передано.

#3 Коды Хемминга

Опишем один из классов групповых кодов- кодов Хемминга, которые исправляют однократную ошибку. Поскольку минимальный вес кодового слова равен 3. Это (m,n) коды, где m=2^r-1-r; n=2^r-1 r≥2.

Схема кодирования:

1) Сообщение – это слова длины 2^r-1-r, r≥2, а кодовые слова имеет длину 2^r-1. В каждом кодовом слове b=b_1b_2…b^r__2-1.

2) В каждом слове, те символы, индексы которых являются степенью двойки b₂⁰b₂¹…; - контрольные, остальные – символы исходного сообщения, расположенные в том же порядке.

П₁ Определить контрольные и символы для r=4. Длина – b₁-b₁₅. Контрольные – b1,b2b4,b8. Остальные – b3,b5,b6,b7,b9,b10,b11 – символы сообщения.

3) Рассмотрим матрицу М порядка r*(2^r-1), такую, что в i-ом столбце этой матрицы стоят символы двоичного разложения числа i. Тогда матрица M при r=2 имеет вид: M_2,3=

1=2⁰-01

2=1*2^1+0*2^0

3=1*2^1+1*2^0

4=1*2^2+0*2+0*2 100

110;111

4) Запишем систему уравнений b*M^t=0 при r=3. b₄₊b_5+b_6+b_4=0

b_2+b_3+b_6+b_7=0

b_1+b_3+b_5+b_7=0

Заметим, что по построению матрицы М входит один и только один символ b₂i, индекс которого есть степень двойки.

5) При кодировании сообщения контрольных символов b_2Ob_2^1…b₂

Схема декодирования:

Пусть принятое слово – С, B – кодирования, L – ошибка, тогда и следовательно b*M^t=0. Если m и t равно 0, то считаем, что ошибки не было при L=0. Если произошла ошибка ровно в одной позиции, т.е. вектор ошибок L имеет только одну единицу в i-ой позиции, то LMT есть вектор, совпадающий с i-ым столбцом матрицы М. Тогда необходимо исправить ошибку в i-ой позиции полученного сообщения, т.е. заменить символ 0 или 1 на противоположный. После этого необходимо вычеркнуть все символы с номерами степенями двойки и из оставшихся символов получить оставшееся слово.

П₂ Применим (37) код Хемминга для кодировки слова А=0111 (r=3, b(кодовое слово)=b_3,b_5,b_6,b_7). Система уравнений: b_4+1+1+1=0

b_2+0+1+1=0

b_1+0+1+1=0. b_1=0, b_2=0,b_4=1

Длина сообщения 2^r-1-r=4. 2^r-r=5. r=3. b_1b_2b_3=0b_4b_5=1b_6=1b_7=1

(b_1b_2b_3b_4b_5b_6b_7)

(1,7)*(7,3)(1,3), транспонируем

Ответ: 0001111.

П₃ Предположим, что получено сообщение C=0011111. C*M^t=lM^t

(0011111)(

) =

П₄ A=0101.Найти кодовое слово

b_1(za4)b_2(za4)b_3b_4(za4)b_5b_6b_7

b_3=0 b_5=1 b_6=0 b_7=1

b_4+1+0+1=0 b_4=0

b_2+0+0+1=0 b_2=1 0⁶1⁵0⁴0³1²0¹1⁰_2=2⁰+2²+2⁵=5+32=37

b_1+0+1+1=0 b_1=0

П₅ C=1010111. C*M^t=lM^t 1010111*

=

=1+1+1=1

1+1+1=1

1+1+1+1=0.

Не нашли, что искали? Воспользуйтесь поиском по сайту: