ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
+- -+ -- -3,-1 ++ ++ -4 -4 4 4 -+ +- 2 2 -2 -2 s 1 s 0 s 2 s 3 s 1 s 0 s 2 s 3 t=0 t=1 Продолжая аналогичным образом, далее получим s 0 → s 0 : (+1, +1) · (−3, −1) = (+1) · (−3) + (+1) · (−1) = −3 − 1 = −4, s 0 → s 2 : ( −1, −1) · (−3, −1) = (−1) · (−3) + (−1) · (−1) = +3 + 1 = +4, s 1 → s 0 : ( −1, −1) · (−3, −1) = (−1) · (−3) + (−1) · (−1) = +3 + 1 = +4, s 1 → s 2 : (+1, +1) · (−3, −1) = (+1) · (−3) + (+1) · (−1) = −3 − 1 = −4, s 2 → s 1 : ( −1, +1) · (−3, −1) = (−1) · (−3) + (+1) · (−1) = +3 − 1 = +2, s 2 → s 3 : (+1, −1) · (−3, −1) = (+1) · (−3) + (−1) · (−1) = −3 + 1 = −2, s 3 → s 1 : (+1, −1) · (−3, −1) = (+1) · (−3) + (−1) · (−1) = −3 + 1 = −2, s 3 → s 3 : ( −1, +1) · (−3, −1) = (−1) · (−3) + (+1) · (−1) = +3 − 2 = +2. 3.4. Сверточные коды 127 4 4 2 2 0 0 0 0 t=0 t=1 Теперь нам необходимо выбрать те ребра, которые дают максимальные значения метрик узлов. На данном шаге это все положительные значения метрик. Выделим их жирным цветом: На втором шаге t = 2 принятая информационная пара есть (0,-1). Тогда, для переходов s i → s k соответствующие скалярные произведения дают s 0 → s 0 : (+1, +1) · (0, −1) = 0 + 1 = −1, s 0 → s 2 : ( −1, −1) · (0, −1) = 0 + 1 = +1, s 1 → s 0 : ( −1, −1) · (0, −1) = 0 + 1 = +1, s 1 → s 2 : (+1, +1) · (0, −1) = 0 − 1 = −1, s 2 → s 1 : ( −1, +1) · (0, −1) = 0 − 1 = −1, s 2 → s 3 : (+1, −1) · (0, −1) = 0 + 1 = +1, s 3 → s 1 : (+1, −1) · (0, −1) = 0 + 1 = +1, s 3 → s 3 : ( −1, +1) · (0, −1) = 0 − 1 = −1. +- -+ -- 0,-1 ++ ++ -1 1 -1 1 -+ +- 1 -1 -1 1 s 1 s 0 s 2 s 3 s 1 s 0 s 2 s 3 t=1 t=2 4 4 2 2 0 0 0 0 3 5 3 5 t=0 t=1 t=2 Теперь нам необходимо выбрать те ребра, которые дают максимальные значения суммарных метрик узлов. Выделим их жирным цветом. На третьем шаге t = 3 принятая информационная пара есть (-1,1). Тогда, для переходов s i → s k соответствующие скалярные произведения дают s 0 → s 0 : (+1, +1) · (−1, 1) = −1 + 1 = 0, s 0 → s 2 : ( −1, −1) · (−1, 1) = +1 − 1 = 0, s 1 → s 0 : ( −1, −1) · (−1, 1) = +1 − 1 = 0, s 1 → s 2 : (+1, +1) · (−1, 1) = −1 + 1 = 0, s 2 → s 1 : ( −1, +1) · (−1, 1) = +1 + 1 = 2, s 2 → s 3 : (+1, −1) · (−1, 1) = −1 − 1 = −2, s 3 → s 1 : (+1, −1) · (−1, 1) = −1 − 1 = −2, s 3 → s 3 : ( −1, +1) · (−1, 1) = +1 + 1 = 2. +- -+ -- -1,1 ++ ++ 0 0 0 0 -+ +- -2 2 2 -2 s 1 s 0 s 2 s 3 s 1 s 0 s 2 s 3 t=2 t=3 128 Глава 3. Теория помехоустойчивого кодирования 4 4 2 2 0 0 0 0 3 3 7 7 3 5 3 5 t=0 t=1 t=2 t=3 Складывая веса полученных узлов с предыдущими значениями нам необходимо выбрать те ребра, которые дают максимальные значения суммарных метрик узлов. Выделим их жирным цветом. Продолжая аналогичным образом, получим следующую последовательность действий. На четвертом шаге t = 4 принятая информационная пара есть (2,-1). s 0 → s 0 : (+1, +1) · (2, −1) = +2 − 1 = +1, s 0 → s 2 : ( −1, −1) · (2, −1) = −2 + 1 = −1, s 1 → s 0 : ( −1, −1) · (2, −1) = −2 + 1 = −1, s 1 → s 2 : (+1, +1) · (2, −1) = +2 − 1 = +1, s 2 → s 1 : ( −1, +1) · (2, −1) = −2 − 1 = −3, s 2 → s 3 : (+1, −1) · (2, −1) = +2 + 1 = +3, s 3 → s 1 : (+1, −1) · (2, −1) = +2 + 1 = +3, s 3 → s 3 : ( −1, +1) · (2, −1) = −2 − 1 = −3. +- -+ -- 2,-1 ++ ++ 1 -1 1 -1 -+ +- 3 -3 -3 3 s 1 s 0 s 2 s 3 s 1 s 0 s 2 s 3 t=3 t=4 На пятом шаге t = 5 принятая информационная пара есть (-4,-2). s 0 → s 0 : (+1, +1) · (−4, −2) = −4 − 2 = −6, s 0 → s 2 : ( −1, −1) · (−4, −2) = +4 + 2 = +6, s 1 → s 0 : ( −1, −1) · (−4, −2) = +4 + 2 = +6, s 1 → s 2 : (+1, +1) · (−4, −2) = −4 − 2 = −6, s 2 → s 1 : ( −1, +1) · (−4, −2) = +4 − 2 = +2, s 2 → s 3 : (+1, −1) · (−4, −2) = −4 + 2 = −2, s 3 → s 1 : (+1, −1) · (−4, −2) = −4 + 2 = −2, s 3 → s 3 : ( −1, +1) · (−4, −2) = +4 − 2 = +2. +- -+ -- -4,-2 ++ ++ -6 6 -6 6 -+ +- -2 2 2 -2 s 1 s 0 s 2 s 3 s 1 s 0 s 2 s 3 t=4 t=5 3.4. Сверточные коды 129 На шестом шаге t = 6 принятая информационная пара есть (3,-1). s 0 → s 0 : (+1, +1) · (3, −1) = +3 − 1 = +2, s 0 → s 2 : ( −1, −1) · (3, −1) = −3 + 1 = −2, s 1 → s 0 : ( −1, −1) · (3, −1) = −3 + 1 = −2, s 1 → s 2 : (+1, +1) · (3, −1) = +3 − 1 = +2, s 2 → s 1 : ( −1, +1) · (3, −1) = −3 − 1 = −4, s 2 → s 3 : (+1, −1) · (3, −1) = +3 + 1 = +4, s 3 → s 1 : (+1, −1) · (3, −1) = +3 + 1 = +4, s 3 → s 3 : ( −1, +1) · (3, −1) = −3 − 1 = −4. +- -+ -- 3,-1 ++ ++ 2 -2 2 -2 -+ +- 4 -4 -4 4 s 1 s 0 s 2 s 3 s 1 s 0 s 2 s 3 t=5 t=6 В результате треллис будет выглядеть следующим образом. 4 4 2 2 0 0 0 0 3 3 7 7 3 5 3 5 t=0 t=1 t=2 t=3 6 8 10 6 16 12 10 8 t=4 t=5 t=6 18 14 12 16 На последнем шаге t = 6 мы выбираем узел с максимальным весом 18 и выделяем единственный путь, по которому к нему можно прийти из t = 0. Как и в жесткой схеме, обозначая верхнее ребро через 0, а нижнее через 1 декодируем принятую комбинацию: 1 1 1 0 0 0 s 1 s 0 s 2 s 3 1 1 1 0 1 1 0 0 0 0 0 Мы получили информационную последовательность a = (111000). N Вопрос. Прежде чем решать следующую задачу, разберитесь почему на 4 шаге верхний путь ( веса 3) имеет обрыв? 4 4 2 2 0 0 0 0 3 3 7 7 3 5 3 5 t=0 t=1 t=2 t=3 6 8 10 6 16 12 10 8 t=4 t=5 t=6 18 14 12 16 130 Глава 3. Теория помехоустойчивого кодирования Задача 3.16. Декодировать сообщение F с помощью мягкого алгоритма Витерби. N F 1 −4, −5, −1, 1, 3, 0, 3, 2, 4, 0, −8, −9, −1, 3, −1, 0 2 −5, 4, 0, 3, −2, −4, 1, 2, 3, 1, 8, 9, 3, −2, 2, 0 3 6, −7, 2, −1, 4, −2, −2, 4, 3, 1, 8, −7, 1, −3, −3, −9 4 8, 7, −2, 3, 4, −4, 3, 4, 2, −1, 6, 7, 2, 0, −4, −9 5 9, −8, 2, 3, 4, −4, −4, −4, −4, 2, −6, 5, −1, 2, 5, −8 6 7, −8, 3, 2, −2, 2, −2, 2, −3, −3, 6, −5, 2, 1, 6, −8 7 7, 6, 3, 0, 3, −1, 1, 0, −4, −3, −6, −7, 3, 0, −7, 7 8 −6, −7, −1, −3, 2, −2, 4, 3, 0, −2, −8, −7, 1, −2, −8, 7 9 8, −7, −3, −1, −3, 1, −3, −3, −3, 1, −8, 9, −1, 3, −9, 6 10 −8, 9, 2, −3, −3, 1, −4, 1, −3, 4, 8, −9, 2, 0, −8, 6 11 8, 9, −3, −2, 2, −3, −2, −4, −4, −4, 8, −7, −3, 1, 7, −5 12 8, 7, −2, −3, 4, −4, 4, 3, 2, 4, 6, 7, 0, −3, 6, −5 13 −6, −7, 3, 0, 2, −2, −1, −2, 4, −2, 6, −5, 3, −2, 5, −4 14 6, −7, 1, 3, 3, 4, 3, −3, 4, −2, 6, −5, 2, 1, 4, −3 15 −8, 7, 1, 3, 1, 0, 4, −3, 3, 1, −6, −7, 2, 1, −3, 2 16 8, −9, 2, −3, 2, 4, −3, 3, −1, 4, −6, 7, 3, 2, −2, 2 17 8, −9, 2, −3, 1, −4, −3, 4, −3, 4, 6, 7, 0, 3, −1, 1 18 −8, −7, 3, −2, 4, −2, −1, 1, 2, 3, 8, −7, −3, −2, 1, 1 19 −6, −7, 3, 2, 4, 1, −1, 0, 4, 2, −8, −9, −3, −2, −2, −2 20 6, 5, 0, 1, −1, 4, −1, −2, 3, −3, 8, 9, 3, 2, 3, −2 21 4, 5, −1, −2, 0, 3, −2, −2, 3, 4, 8, −7, −1, −2, −4, −3 22 −5, −6, 1, 2, 2, 3, −3, −1, −2, 0, −6, −7, −3, −3, 5, −3 23 7, 6, 0, 3, 3, −2, −3, 4, 0, 4, 6, 5, −3, 2, −6, 4 24 −7, 8, 2, 1, −3, −3, 0, 1, 0, −4, −6, 5, −2, 3, 7, 4 25 −9, 8, −3, 3, 0, −4, −1, −2, 2, −1, −6, −7, −1, 3, −8, 5 26 −9, 8, −1, −3, 0, 4, −4, −1, 2, −1, 8, −7, 3, 1, 9, 5 27 7, −8, 2, 1, −4, −3, 3, 2, −4, 1, −8, −9, 3, −1, −0, −6 28 7, −6, 2, −3, −2, 3, 1, −3, −2, 0, 8, −9, 2, 3, −9, −6 29 8, 7, 3, 0, −3, 4, 3, 0, −1, −3, −8, −7, −2, −1, 8, −7 30 −8, −9, −2, 3, −4, −1, 0, 1, −1, −1, −6, 7, −3, 0, 7, −7 3.5. Турбокоды 131 3.5 Турбокоды Турбокоды были введены в практику в 1993 г. и по существу являются комбинацией двух сверточных кодов. Они обеспечивают значения достоверности очень близкое к пределу Шеннона. Турбокоды в настоящее время приняты в качестве стандарта для систем связи телекоммуникаций третьего поколения 3GPP, стандарта сотовой связи CDMA-2000, цифрового телевидения DVB, используются в системах спутниковой связи VSAT и во многих др. стандартах. Как и в случае мягкого декодирования Витерби, логические элементы 0 и 1 мы будем представлять электрическим напряжением (-1) и (+1). Проверочные символы для информационной последовательности a = (x 1 , x 2 , x 3 , x 4 ) строятся следующим образом. Представим последовательность x k в виде матрицы L = L 1 L 2 L 3 L 4 = x 1 x 2 x 3 x 4 x 12 x 34 , ( x 13 x 24 ) где горизонтальные и вертикальные проверочные символы строятся следующим образом x 12 x 34 = x 1 ⊕ x 2 x 3 ⊕ x 4 , x 13 x 24 = x 1 ⊕ x 3 x 2 ⊕ x 4 Передаваемая кодовая комбинация имеет вид F = (x 1 , x 2 , x 3 , x 4 , x 12 , x 34 , x 13 , x 24 ). Итерационный метод декодирования заключается в следующем. 1. На первом шаге мы вычисляем горизонтальную невязку проверочных символов H = H 1 H 2 H 3 H 4 = x 2 x 12 x 1 x 12 x 4 x 34 x 3 x 34 Здесь новая операция определяется следующим образом A B = ( −) · sign(A) · sign(B) · min(|A|, |B|). 2. На втором шаге вычисляются вертикальные невязки проверочных символов V = V 1 V 2 V 3 V 4 = (L 3 + H 3 ) x 13 (L 4 + H 4 ) x 24 (L 1 + H 1 ) x 13 (L 2 + H 2 ) x 24 Результатом первой итерации является матрица X 1 = L + H + V. 132 Глава 3. Теория помехоустойчивого кодирования 3. На третьем шаге мы опять вычисляем горизонтальную невязку проверочных символов H = (L 2 + V 2 ) x 12 (L 1 + V 1 ) x 12 (L 4 + V 4 ) x 34 (L 3 + V 3 ) x 34 Заметим, что элементы матрицы V мы берем с предыдущего 2 шага. 4. На четвертом шаге вычисляются вертикальные невязки проверочных символов V = V 1 V 2 V 3 V 4 = (L 3 + H 3 ) x 13 (L 4 + H 4 ) x 24 (L 1 + H 1 ) x 13 (L 2 + H 2 ) x 24 Заметим, что элементы матрицы H мы берем с предыдущего 3 шага. Результатом второй итерации является матрица X 2 = L + H + V. Как и во всех итеррационных алгоритмах нам периодически требуется проверить насколько сильно изменяются результаты вычислений при последующих итерациях. Если X k ≈ X k−1 то процесс вычисления можно прекращать, обозначив X = X k Если же значения X k сильно отличаются от X k−1 , то необходимо повторять шаги 3- 4. На заключительном этапе нам необходимо перейти от мягкого решения к жесткому ответу. Для этого всем отрицательным компонентам матрицы X = X 1 X 2 X 3 X 4 ставятся в соответсвие значения принимаемого сигнала 0, а всем положительным - значение 1: a = 1/2 + 1/2sign(x) или a = 1 2 1 + sign(X 1 ) 1 + sign(X 2 ) 1 + sign(X 3 ) 1 + sign(X 4 ) Пример 3.23. Закодируем сообщение a = (1011). Решение. Учитывая, что a = (x 1 , x 2 , x 3 , x 4 ) = (1011) представим последовательность x k в виде матрицы L = x 1 x 2 x 3 x 4 = 1 0 1 1 , тогда горизонтальные и вертикальные проверочные символы строятся следующим образом x 12 x 34 = x 1 ⊕ x 2 x 3 ⊕ x 4 = 1 ⊕ 0 1 ⊕ 1 = 1 0 x 13 x 24 = x 1 ⊕ x 3 x 2 ⊕ x 4 = 1 ⊕ 1 0 ⊕ 1 = 0 1 Передаваемая кодовая комбинация имеет вид F = (x 1 , x 2 , x 3 , x 4 , x 12 , x 34 , x 13 , x 24 ) = (10111001). N Процесс кодирования изобразим следующим образом: 3.5. Турбокоды 133 1 0 1 1 t dB 1 0 0 1 1 1 0 1 t dB Информационная последовательность. Кодовая последовательность. В процессе передачи информации последовательность искажается как в следствие различных помех, так и в следствие естественного затухания электромагнитных волн. Принимаемый сигнал может иметь следующий вид: dB t Если приемник фиксирует только знак напряженности электромагнитного поля, то цифровая аппроксимация сигнала будет такой. 1 0 0 0 1 1 0 0 t dB Другими словами, мы получили кодовую комбинацию в виде F = ( 00111000) т.е. с двумя ошибками. Теперь рассмотрим алоритм мягкого декодирования. Для этого введем 10 уровневое квантование сигнала и запишем его в виде 134 Глава 3. Теория помехоустойчивого кодирования 0,8 0,3 0,3 0,5 0,7 0,9 0,4 t 0,5 F= dB 0,3 0,5 0,7 0,9 0,1 Из рисунка видно, что принятая кодовая комбинация теперь имеет вид F = (0.4, 0.5, 0.8, 0.9, 0.7, 0.3, 0.3, 0.5). Пример 3.24. Декодировать принятую кодовую комбинацию F = (0.4, 0.5, 0.8, 0.9, 0.7, 0.3, 0.3, 0.5). Решение. Выделим из принятой информационной последовательности F = (x 1 , x 2 , x 3 , x 4 , x 12 , x 34 , x 13 , x 24 ) = (0.4, 0.5, 0.8, 0.9, 0.7, 0.3, 0.3, 0.5) информационную матрицу L = x 1 x 2 x 3 x 4 = 0.4 0.5 0.8 0.9 , горизотнальные (x 12 , x 34 ) и вертикальные (x 13 , x 24 ) проверочные символы x 12 x 34 = 0.7 0.3 , x 13 x 24 = 0.3 0.5 1. На первом шаге мы вычисляем горизонтальную невязку проверочных символов H = x 2 x 12 x 1 x 12 x 4 x 34 x 3 x 34 = 0.5 0.7 0.4 0.7 0.9 0.3 0.8 0.3 Учитывая, что A B = ( −1) · sign(A) · sign(B) · min(|A|, |B|) 3.5. Турбокоды 135 получим x 2 x 12 = 0.5 0.7 = ( −1) · sign(0.5) · sign(0.7) · min(|0.5|, |0.7|) = −0.5, x 1 x 12 = 0.4 0.7 = ( −1) · sign(0.4) · sign(0.7) · min(|0.4|, |0.7|) = −0.4, x 4 x 34 = 0.9 0.3 = ( −1) · sign(0.9) · sign(0.3) · min(|0.9|, |0.3|) = −0.3, x 3 x 34 = 0.8 0.3 = ( −1) · sign(0.8) · sign(0.3) · min(|0.8|, |0.3|) = −0.3, и H = H 1 H 2 H 3 H 4 = −0.5 −0.4 −0.3 −0.3 2. На втором шаге вычисляем вертикальную невязку проверочных символов V = (L 3 + H 3 ) x 13 (L 4 + H 4 ) x 24 (L 1 + H 1 ) x 13 (L 2 + H 2 ) x 24 = (0.8 − 0.3) 0.3 (0.9 − 0.3) 0.5 (0.4 − 0.5) 0.3 (0.5 − 0.4) 0.5 или V = V 1 V 2 V 3 V 4 = −0.3 −0.5 0.1 −0.1 Результатом первой итерации является матрица X 1 = L+H+V = 0.4 0.5 0.8 0.9 + −0.5 −0.4 −0.3 −0.3 + −0.3 −0.5 0.1 −0.1 = −0.4 −0.4 0.6 0.5 3. На третьем шаге мы опять вычисляем горизонтальную невязку проверочных символов H = (L 2 + V 2 ) x 12 (L 1 + V 1 ) x 12 (L 4 + V 4 ) x 34 (L 3 + V 3 ) x 34 = (0.5 − 0.5) 0.7 (0.4 − 0.3) 0.7 (0.9 − 0.1) 0.3 (0.8 + 0.1) 0.3 Заметим, что элементы матрицы V мы берем с предыдущего 2 шага. В результате получаем H = 0 0.7 0.1 0.7 0.8 0.3 0.9 0.3 = 0 −0.1 −0.3 −0.3 4. На четвертом шаге вычисляем вертикальную невязку проверочных символов V = V 1 V 2 V 3 V 4 = (L 3 + H 3 ) x 13 (L 4 + H 4 ) x 24 (L 1 + H 1 ) x 13 (L 2 + H 2 ) x 24 Подставляя сюда элементы матрицы H с предыдущего 3 шага, получим V = (0.8 − 0.3) 0.3 (0.9 − 0.3) 0.5 (0.4 + 0) 0.3 (0.5 − 0.1) 0.5 = 0.5 0.3 0.6 0.5 0.4 0.3 0.4 0.5 , или V = −0.3 −0.5 −0.3 −0.4 |