ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
1 10 01 01 00 10 00 11 11 1 10 01 01 00 10 00 11 11 0 10 01 01 00 10 00 11 11 1 10 01 01 00 10 00 11 11 1 10 01 01 00 10 00 11 11 1 10 01 01 00 10 00 11 11 0 10 01 01 00 10 00 11 11 0 10 01 01 00 10 00 11 11 10 01 01 00 10 F= 11 01 01 00 01 10 01 11 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 s 0 s 1 s 2 s 3 a = Треллис для кодовой последовательности F = (11, 01, 01, 00, 01, 10, 01, 11) показан на рисунке. Декодирование полученной кодовой последовательности производится в обратном порядке. Пример 3.17. Раскодировать последовательность F = (00, 11, 10, 11, 11, 10, 00, 01, 10, 01, 11). Решение. Начиная из узла s 0 треллиса мы на кждом шаге будем выбирать ребро с весом, соответствующим полученной кодовой комбинации. Так для первой пары символов мы имеем значения 00. Для треллиса это соответствует верхнему ребру выходящему из узла s 0 при t=0. Мы перешли в ребро s 0 при t=1. Для второй пары принятой кодовой комбинации мы имеем 11. Т.к. мы находимся в узле s 0 при t=1, то с весом 11 у нас имеется только нижнее ребро и мы переходим в узел s 2 (на t=2). Для третьей пары принятой кодовой комбинации мы имеем 10. Поскольку мы теперь находимся в узле s 2 (при t=2) то с весом 10 из него выходит только верхнее ребро. Мы выбираем ребро 10 и переходим на узел s 1 (t=3). Четвертая пара имеет значение 11. Поскольку мы теперь находимся в узле s 1 (при t=3) то с весом 11 у нас имеется только верхнее ребро. Мы переходим по ребру 11 в узел s 0 и т.д. F= 00 11 10 11 11 10 00 01 10 01 11 a= 0 1 0 0 1 0 1 1 1 0 0 s 0 s 1 s 2 s 3 3.4. Сверточные коды 117 Прочертив жирным следом весь путь треллиса можно приступить к раскодированию сообщения. Каждый узел треллиса имеет два выходящих ребра: верхнее и нижнее. Если для данного узла выделенный путь пошел через верхнее ребро, то информационный символ принимает значение 0. Если для данного узла выделенный путь пошел через нижнее ребро, то информационный символ принимает значение 1. В нашем случае выходная информационная последовательность принимает вид a = (01001011000). N Задача 3.14. Построить сверточный код для двоичной последовательности ASCII кода первой буквы своей фамилии. 3.4.4 Коррекция ошибок сверточным кодом Как было показано выше каждой кодовой комбинации соответствует свой путь в треллисе. Однако обратное не верно. Не для всякой полученной последовательности можно начертить путь в треллисе. Например не существует пути для такой комбинайии как F = (11, 11, 11) или F = (01, 01, 01). Так же нет кодовых комбинаций, начинающихся с 01 или 10. Такие пары в F свидетельствуют о наличии ошибок. Искажение двоичной кодовой последовательности при передаче по каналу информации с помехами заключается в изменении значения некоторого бита на противоположное. Если ниформация кодируется блоками, то количество ошибок в блоке равно количеству несовпадений между принятым словом и исходным. Напомним, что расстояние между сообщениями определяется как количество несовпадающих разрядов. Поэтому каждая ошибка в передаваемой кодовой комбинации увеличивает ее расстояние от исходного значения. Соответственно новая, искаженная кодовая комбинация будет иметь искаженный путь треллиса. А в некоторых ситуациях пути может и не быть. Задача коррекции ошибки заключается в построении для F множества возможных путей и выбора среди них такого, который имеет минимальное расстояние с полученной кодовой комбинацией F . Пример 3.18. Передаваемое информационное сообщение имеет вид a = (1010). Этому сообщению соответствует следующая кодовая комбинация F = (11, 10, 00, 01). a = 1 0 1 0 F= 11 10 00 10 t=0 t=1 t=2 t=3 t=4 11 10 00 10 s 0 s 1 s 2 s 3 Допустим в передаваемой комбинации возникла ошибка F (x) = (11, 1 1, 00, 10). Необходимо восстановить информационную последовательность. 118 Глава 3. Теория помехоустойчивого кодирования F= 11 t=0 t=1 11 s 0 s 1 s 2 s 3 Решение. Начиная из узла s 0 (t=0) треллиса мы выбирем ребро с весом, соответствующим полученной кодовой комбинации F (x). Так для первой пары символов мы имеем значения 11. Для треллиса это соответствует нижнему ребру выходящему из узла s 0 . Мы перешли в узел s 2 при t=1. На втором шаге из узла s 2 (t=1) треллиса мы должны выбрать ребро с весом 11, соответствующим второй паре полученной кодовой комбинации F (x). Так как ребер с таким весом у нас нет, то мы рассмотрим оба имеющихся варианта. Для верхнего ребра имеем вес 10. Запишем расстояние между 10 и 11 в узел s 1 (t=2). Для нижнего ребра имеем вес 01. Расстояние между 01 и 11 равно 1 - запишем в узел s 3 (t=2). F= 11 11 t=0 t=1 t=2 10 01 1 1 s 0 s 1 s 2 s 3 F= 11 11 00 t=0 t=1 t=2 t=3 11 10 01 1 1 11 00 10 01 2 0 1 1 s 0 s 1 s 2 s 3 Третья пара принятой комбинации имеет значение 00. На третьем шаге мы имеем два маршрута. Из узла s 1 (t=2) треллиса выходят 2 ребра с весом 11 и 00. Расстояния между ними и принятым значением запишем в соответствующих узлах: 2-для s 0 и 0-для s 2 . Из узла s 3 также выходят два ребра с весом 01 и 10. Расстояние между ними и принятым знчением 00 равно 1 записывается в узлы s 1 и s 3 (t=3). F= 11 11 00 10 t=0 t=1 t=2 t=3 t=4 10 s 0 s 1 s 2 s 3 0 На 4 шаге нам необходимо отбросить узлы с максимальным весом, поскольку они соответствуют последовательностям наиболее сильно отличающимся от передаваемой. Для дальнейшего пути мы оставляем только узел s 2 . Четвертая пара принятой комбинации имеет значение 10. Из узла s 2 (t=3) треллиса выходит верхнее ребро с весом 10 и мы переходим по этому ребру в узел s 1 3.4. Сверточные коды 119 В заключение мы должны определить путь проходящий через узлы с минимальным суммарным растоянием. На каждом шаге, верхнему ребру мы ставим в соответствие значение 0, а нижнему ребру значение 1. Раскодированная информационная последовательность имеет вид a = (1010). N a = 1 0 1 0 t=0 t=1 t=2 t=3 t=4 1 0 1 0 1 0 1 0 s 0 s 1 s 2 s 3 Пример 3.19. Передаваемое информационное сообщение имеет вид a = (111000101). Этому сообщению соответствует следующая кодовая комбинация, построенная по стреллису: F = (11, 01, 10, 01, 11, 00, 11, 10, 00). a = 1 1 1 0 0 0 1 0 1 F= 11 01 10 01 11 00 11 10 00 t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 11 s 0 s 1 s 2 s 3 01 01 11 11 00 00 10 10 Допустим в передаваемой комбинации возникло несколько ошибок F = ( 01, 01, 11, 01, 10, 00, 10, 10, 00). Необходимо восстановить информационную последовательность. s 0 s 1 s 2 s 3 11 00 t=0 t=1 1 1 F= 01 Решение. Начиная из узла s 0 (t=0) треллиса мы должны выбрать ребро с весом, соответствующим полученной кодовой комбинации F (x). Так для первой пары символов мы имеем значения 01. Однако из узла s 0 не выходит ребер с таким весом. Но есть ребра с весами 00 и 11. Нам необходимо рассмотреть оба имеющихя варианта. Вес верхнего ребра 00. Запишем в узел s 0 (t=1) расстояние между весом ребра 00 и значением первой пары 01 кодовой комбинации. В узел s 2 (t=1) так же записывается значение 1 - расстояние между весом нижнего ребра 11 и кодом 01. 120 Глава 3. Теория помехоустойчивого кодирования Вторая пара пара принятой комбинации имеет значение 01. Нам необходимо продолжить уже два маршрута. Из узла s 0 (t=1) треллиса выходят 2 ребра с весом 11 и 00. Расстояния между ними и принятым значением 01 запишем в соответствующих узлах: 2-для s 0 и 0-для s 2 Из узла s 2 также выходят два ребра с весом 01 и 10. Расстояние между ними и принятым знчением 00 равное 1 записывается в узлы s 1 и s 3 (t=2). t=0 t=1 t=2 1 00 00 11 11 10 01 1 1 1 2 0 s 0 s 1 s 2 s 3 01 01 Теперь нам нам необходимо отбросить узлы с максимальным расстоянием, поскольку они соответствуют последовательностям наиболее сильно отличающимся от передаваемой. Поскольку s 3 - узел с минимальным расстоянием =0, то дальнейший маршрут мы будем прокладывать от него. t=0 t=1 t=2 t=3 s 0 s 1 s 2 s 3 01 01 11 10 01 1 1 На третьем шаге из узла s 3 (t=2) мы должны выбрать ребро с весом 11. Так как ребер с таким весом у нас нет, то мы рассмотрим маршруты по ребрам с весом 01 и 10. Запишем расстояние между 01 и 11 в узел s 1 (t=3). Для нижнего ребра имеем вес 10. Расстояние между 10 и 11 равно 1 - запишем в узел s 3 (t=3). Следующая пара принятой комбинации имеет значение 01. Нам необходимо продолжить уже два маршрута. Из узла s 1 (t=3) выходят 2 ребра с весом 11 и 00. Расстояния между ними и принятым значением 01 запишем в соответствующих узлах: 1-для s 0 и s 2 . Из узла s 3 также выходят два ребра с весами 01 и 10. Расстояние между ними и принятым значением 01 записывается в узелы s 1 (0) и s 3 (2). t=0 t=1 t=2 t=3 t=4 s 0 s 1 s 2 s 3 01 01 11 10 01 1 1 01 01 10 00 11 1 0 2 1 Далее, отбрасываем узлы с максимальным расстоянием поскольку они соответствуют последовательностям наиболее сильно отличающимся от передаваемой. Поскольку s 1 - узел с минимальным расстоянием =0, то дальнейший маршрут мы будем прокладывать от него. 3.4. Сверточные коды 121 t=0 t=1 t=2 t=3 t=4 01 01 11 01 s 0 s 1 s 2 s 3 01 10 01 10 11 00 1 0 1 2 На пятом шаге из узла s 1 (t=4) мы должны выбрать ребро с весом 10. Так как ребер с таким весом у нас нет, то мы рассмотрим маршруты по ребрам с весом 11 и 00. Запишем расстояние между 11 и 10 в узел s 0 (t=5). Для нижнего ребра имеем вес 00. Расстояние между 00 и 10 равно 1 - запишем в узел s 3 (t=5). Дальнейший ход расчетов покажем на рисунках. t=0 t=1 t=2 t=3 t=4 t=5 01 01 11 01 s 0 s 1 s 2 s 3 10 11 00 1 1 t=0 t=1 t=2 t=3 t=4 t=5 t=6 01 01 11 01 s 0 s 1 s 2 s 3 10 11 00 1 1 00 00 11 10 01 2 1 1 0 t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 01 01 11 01 s 0 s 1 s 2 s 3 10 00 10 00 11 1 1 t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 01 01 11 01 s 0 s 1 s 2 s 3 10 00 10 00 11 1 1 10 00 11 10 01 2 1 1 0 122 Глава 3. Теория помехоустойчивого кодирования t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 01 01 11 01 10 00 10 10 10 10 0 В заключение мы должны определить путь проходящий через узлы с минимальным суммарным растоянием. На каждом шаге, верхнему ребру мы ставим в соответствие значение 0, а нижнему ребру значение 1. t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 1 s 0 s 1 s 2 s 3 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 Раскодированная информационная последовательность имеет вид a = (111000101). N Как видно из последнего примера количество ошибок в последовательности может быть любым, главное, чтобы они отстояли друг от друга не менее чем на 5 символов. Т.е. между двумя искаженными значениями должно стоять не менее 4 неискаженных. Но это означает, что для обнаружения ошибки мы должны рассчитать расстояния по всем узлам за последние 2 шага. Очевидно, что чем плотнее расположены ошибки тем труднее их будет обнаружить и тем большее количество шагов необходимо учитывать для рассчета расстояния. Количество шагов, используемых для рассчета расстояний называется шириной окна декодирования. Рассмотрим пример двух последовательных ошибок. Пример 3.20. Передаваемое информационное сообщение имеет вид a = (000000). Этому сообщению соответствует следующая кодовая комбинация, построенная по треллису: F = (00, 00, 00, 00, 00, 00). t=0 t=1 t=2 t=3 t=4 t=5 t=6 00 00 00 00 s 0 s 1 s 2 s 3 00 00 3.4. Сверточные коды 123 Допустим в передаваемой комбинации возникли последовательно две ошибки F = ( 11, 00, 00, 00, 00, 00). Необходимо восстановить информационную последовательность. Решение. Для обнаружения такой ошибки нам необходимо начертить треллис глубиной до шестого уровня включительно. И только на 6 уровне сумма расстояний по верхнему пути (2) превысит расстояние альтернативного маршрута (3). Здесь ширина окна декодирования равна L=6. t=0 t=1 t=2 t=3 t=4 t=5 t=6 11 00 00 00 s 0 s 1 s 2 s 3 2 0 0 0 1 1 1 0 0 0 0 0 00 00 11 00 11 s 0 s 1 s 2 s 3 00 00 00 Другими словами искажение парной ошибки возможно если после нее идут как минимум 10 неискаженных разрядов. Наряду с этим возможны случаи, когда ошибку вообще невозможно распознать. Например для кода F = (00, 00, 00) совокупность ошибок типа F = (11, 10, 11) приведут к тому, что декодер вместо последовательности a = (000) выдаст сообщение a = (100). К сожалению, в этом случае даже увеличение ширины окна декодирования не позволяет обнаружить ошибку. Такого рода пакеты ошибок мы будем называть жесткими. Несложно показать что минимальный жесткий пакет ошибок имеет вид 3-1-2. Т.е. в произвольной кодовой последовательности начиная с некоторого бита появляется подрят 3 ошибочных, затем 1 неискаженный и наконец еще 2 ошибочных (инвертированных). Например жесткими будут следующие пакеты ошибок F 11 0101111101 → 111011001101 00 11010100 → 0001111000 К счастью все жесткие пакеты ошибок должны начинаться с первого элемента пары, а это в свою очередь также уменьшает вероятность их появления. Пример 3.21. Раскодировать сообщение (ая) используя ширину окна декодирования L ≤ 2. Решение. Сообщению (ая) соответствуют значения (e0,ff) ASCII таблицы. Переведем его в двоичный вид (e0,ff) = (11100000, 11111111). Таким образом исходное кодовое слово имеет вид F = (11, 10, 00, 00, 11, 11, 11, 11). Для раскодирования сообщения воспользуемся треллисом 124 Глава 3. Теория помехоустойчивого кодирования t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 11 10 00 00 s 0 s 1 s 2 s 3 11 11 11 11 0 0 1 0 1 0 1 1 0 1 2 1 1 0 1 1 2 2 2 0 На рисунке показаны несколько альтернативных маршрутов с окном декодирования L=2. Очевидно, что последние 4 пары (11,11,11,11) последовательности обрауют какую-то ошибочную комбинацию. Но для ее исправления у декодера нет дополнительных символов. Поэтому декодер должен либо сообщить о невозможности декодирования, либо предложить некоторую наиболее вероятную комбинацию. В нашем случае, используя жирную линию треллиса получим a = (10100110) 2 = a6 h = | . N Задача 3.15. Раскодировать сообщение F используя ширину окна декодирования L ≤ 2. N F N F N F 1. 0001010101001110 11. 0010010111001110 20. 0011110111101110 2. 0001101100101110 12. 0010101100011110 22. 0011001100000110 3. 1111011100101110 13. 1100011100011110 23. 1101111100000110 4. 1111100100110100 14. 1100100100000100 24. 1101000100011100 5. 1111100100000010 15. 1100100100110010 25. 1101000100101010 6. 1111011111000010 16. 1100011111110010 26. 1101111111101010 7. 1100001000000010 17. 1111001000110010 27. 1110101000101010 8. 1111010001110001 18. 1100010001000001 28. 1101110001011001 9. 0001101111001100 19. 0010101111111100 29. 0011001111100100 10. 0010111000111010 20. 0001111000001010 30. 0000011000010010 3.4.5 Алгоритм Витерби Рассмотрим схему передачи и приема сообщения в канале с помехами сверточным кодом. Допустим информационная последовательность имеет вид a = (111000). Схема кодирования показана на рисунке. 11 01 10 01 11 00 1 1 1 0 0 0 s 1 s 0 s 2 s 3 3.4. Сверточные коды 125 Передаваемая кодовая комбинация имеет вид F = (110110011100). На аппаратном уровне мы можем представить сигнал с положительным напряжением (+) как 0, а сигнал с отрицательным напряжением (-) как 1. Тогда процесс кодирования выглядит следующим образом: 1 1 1 0 0 0 t dB 0 0 0 0 0 1 1 1 1 1 1 1 t dB Информационная последовательность. Кодовая последовательность. В процессе передачи информации последовательность искажается как в следствие различных помех, так и в следствие естественного затухания электромагнитных волн. Принимаемый сигнал может иметь следующий вид: t dB Если приемник фиксирует только знак напряженности электромагнитного поля, то цифровая аппроксимация сигнала будет такой Другими словами, мы получили кодовую комбинацию в виде F = (11 1110011101) т.е. с двумя ошибками. 1 0 0 0 1 1 1 1 1 1 1 t dB 1 11 11 10 01 11 00 s 1 s 0 s 2 s 3 11 10 01 1 1 1 1 0 2 01 01 10 11 01 11 11 00 1 1 Допустим, мы будем придерживаться жесткой схемы декодирования, показанной на треллисе. Тогда декодер сможет исправить одну ошибку в середине последовательности, но не исправит последнюю ошибку, поскольку у него не хватит шагов для увеличения окна декодирования. 126 Глава 3. Теория помехоустойчивого кодирования С вероятностью 1/2 декодер может выдать правильный ответ (111000) или (111001), а возможно выдаст сообщение о невозможности декодирования. Теперь рассмотрим алоритм Витерби мягкого декодирования. Для этого необходимо, чтобы приемник сигнала различал не только знак напряженности, но и амлитуду принимаемого сигнала. Как правило 8 уровневого квантования сигнала бывает достаточно для эффективного применения мягкой схемы декодирования. 0 1 2 3 -1 -2 -4 -1 -1 -1 -3 t dB -1 -1 -3 -2 1 2 0 Из рисунка видно, что принятая кодовая комбинация имеет вид F = ( −3, −1, 0, −1, −1, 1, 2, −1, −4, −2, 3, −1) Пример 3.22. Декодировать принятую кодовую комбинацию F = ( −3, −1, 0, −1, −1, 1, 2, −1, −4, −2, 3, −1). Решение. Расмотрим первый шаг декодирования. Для этого на треллисе обозначим вес ребра (00) символом (+1,+1), вес ребра (11) символом (-1,-1), вес (10) - символом (-1,+1), вес (01) - символом (+1,-1). Это означает, что для вычисления метрики очередного узла нам необходимо найти скалярное произведение веса ребра с принятой информационной парой. На первом шаге t = 1 принятая информационная пара есть (-3,-1). Тогда, для перехода s 0 → s 0 мы должны найти скалярное произведение (+1, +1)·(−3, −1) = (+1)·(−3)+(+1)·(−1) = −3 − 1 = −4. |