|
|
ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ#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, bm+1= 1, 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 ( П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 – символы сообщения.
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)( ) =
П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 - 2023 stydopedia.ru Все материалы защищены законодательством РФ.
|
i – четное число
i) т.е. b1+…+bm+1=0 (mod 2), т.е. если