Сделай Сам Свою Работу на 5

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

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

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

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

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

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

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

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

E: {0;1}m –> {0;1}n

D: {0;1}n –> {0;1}m,

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

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

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

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

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

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

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



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

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

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

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

bm+1=

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

D(b)=c=c1,…,cm. ci=bi, 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) т.е. b1+…+bm+1=0 (mod 2), т.е. если i – нечетна, то при передаче сообщения произошла ошибка, однако если i четная, то еще не означает, что ошибки не было. Подразрядная сумма окажется четной при любом четном числе ошибок.

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

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

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

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

П1 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).

П2 a+b=01101

01010 w(a)=3

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

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

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

В математической модели кодирования и декодирования удобно рассматривать строки ошибок. Данное сообщение А кодируется кодовым словом b= При передаче канал связи добавляет к нему строку ошибок l=l1….ln, что приемник принимает сигнал c=c1…cn, ci=bi+li. Система, исправляющая ошибки переводит слово с1, b1 в ближайшее слово an, bт. Система обнаруживающая ошибки только устанавливает является ли принятое слово кодовым или нет. Последнее означает, что при передаче произошла ошибка.

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

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

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

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

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

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

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

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

0

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

1=20-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*Mt=0 при r=3. b4+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

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

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

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

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

П2 Применим (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

Длина сообщения 2r-1-r=4. 2r-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.

 

 

П3 Предположим, что получено сообщение C=0011111. C*Mt=lMt

(0011111)(

) =

1+ 1++ 1+ 1=
1+ 1+ ++ 1=
1+ ++ 1=

П4 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 06150403120110_2=20+22+25=5+32=37

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

П5 C=1010111. C*Mt=lMt 1010111*


=

=1+1+1=1

1+1+1=1

1+1+1+1=0.

 



©2015- 2017 stydopedia.ru Все материалы защищены законодательством РФ.