ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
H = 0 −0.1 −0.3 −0.3 , V = −0.3 −0.5 −0.3 −0.4 , X 3 = 0.1 −0.1 0.2 0.2 Поскольку X = X 2 = X 3 , то дальнейшие итерации мы прекращаем. На заключительном этапе нам необходимо перейти от мягкого решения к жесткому ответу. Для этого всем отрицательным компонентам матрицы X ставятся в соответсвие значения принимаемого сигнала 0, а всем положительным - значение 1: a = 1 2 1 + sign(X 1 ) 1 + sign(X 2 ) 1 + sign(X 3 ) 1 + sign(X 4 ) = 1 2 1 + sign(0.1) 1 + sign(−0.1) 1 + sign(0.2) 1 + sign(0.2) или a = 1 2 1 + 1 1 − 1 1 + 1 1 + 1 = 1 2 2 0 2 2 = 1 0 1 1 Таким образом, декодированная информационная последовательность имеет вид a = (1011). N Задача 3.17. Декодировать принятые сигналы F , сформированные турбокодом. N F N F 1 0.9, 0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 16 0.8, 0.1, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 2 0.9, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 17 0.8, 0.2, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 3 0.9, 0.3, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 18 0.8, 0.3, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 4 0.9, 0.4, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 19 0.8, 0.4, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 5 0.9, 0.5, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 20 0.8, 0.5, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 6 0.9, 0.6, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 21 0.8, 0.6, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 7 0.9, 0.7, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 22 0.8, 0.7, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 8 0.9, 0.1, 0.1, 0.4, 0.5, 0.6, 0.7, 0.8 23 0.8, 0.8, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 9 0.8, 0.1, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 24 0.8, 0.9, 0.6, 0.8, 0.3, 0.8, 0.6, 0.7 10 0.8, 0.2, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 25 0.8, 0.9, 0.5, 0.8, 0.4, 0.9, 0.5, 0.6 11 0.8, 0.3, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 26 0.8, 0.9, 0.4, 0.8, 0.4, 0.9, 0.5, 0.6 12 0.8, 0.4, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 27 0.8, 0.9, 0.3, 0.8, 0.4, 0.9, 0.5, 0.6 13 0.8, 0.5, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 28 0.8, 0.9, 0.2, 0.8, 0.4, 0.9, 0.5, 0.6 14 0.8, 0.6, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 29 0.8, 0.9, 0.1, 0.8, 0.4, 0.9, 0.5, 0.6 15 0.8, 0.7, 0.7, 0.8, 0.2, 0.7, 0.7, 0.6 30 0.7, 0.8, 0.4, 0.8, 0.4, 0.7, 0.5, 0.7 3.6. Вычисления в полях Галуа 137 3.6 Вычисления в полях Галуа Группой G называется множество элементов (a 1 , a 2 , ..., a n ) ∈ G (с заданной ассоциативной бинарной операцией ” ◦ ” 4 , для которых выполняются следующие условия: 1. a ◦ e = a - существование некоторого единичного элемента e ∈ G; 2. a◦a = e - существование обратного элемента a ∈ G для любого элемента группы a ∈ G. Количество элементов в группе называется порядком группы. Множество целых чисел (..., −3, −2, −1, 0, 1, 2, 3, ...) ∈ Z относительно бинарной операции ”+” (арифметическое сложение) образует группу, поскольку в нем элемент e = 0 играет роль единичного (т.е. a + e = a + 0 = a) и для любого числа a ∈ Z можно найти такое b ∈ Z, что их сумма даст e = 0. Например для a = 4, обратным будет b = −4, тогда a + b = 4 + (−4) = 0 = e. Описанное множество далее будет называться аддитивной группой. Множество тех же целых чисел (..., −3, −2, −1, 0, 1, 2, 3, ...) ∈ Z относительно бинарной операции ”·” (умножение) не образует группу, поскольку в нем нельзя найти обратного элемента для произволного a ∈ Z. Очевидно, что роль единичного элемента здесь будет играть собственно единица e = 1 (т.е. a · e = a · 1 = a), но для нахождения обратного элемента необходимо для произвольного a найти такое b, чтобы выполнялось равенство a · b = e. Например, для a = 5 мы должны написать b = 1 5 = 0.2 и тогда 5 · 0.2 = 1. Но b = 1 5 = 0.2 / ∈ Z т.е. обратное число не является целым и не принадлежит множеству Z. Такое множество элементов называется полугруппой (мультипликативной полугруппой). Для читателя, впервые сталкивающегося с теорией конечных групп естественно возникает вопрос: а что делать если сумма двух элементов группы будет больше максимального элемента группы? Пример 3.25. Классические стрелочные часы имеют на циферблате значения (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12). Если занятия начались в 11 часов и будут длится 2 часа, то во сколько они закончатся? Обычно ответ вычисляется следующим образом 11 + 2 = 13, но числа 13 часах не нарисовано. Тогда мы вычитаем 13 − 12 = 1 и говорим, что занятия закончились в 1 час. 4 Ассоциативность означает, что нам безразлично в каком порядке проводить вычисления: (a 1 ◦ a 2 ) ◦ a 3 = a 1 ◦ (a 2 ◦ a 3 ) = a 1 ◦ a 2 ◦ a 3 138 Глава 3. Теория помехоустойчивого кодирования Пример 3.26. Если мы легли спать в 10 часов и проспали 9 часов, то во сколько мы проснулись? Вычисляя 10 + 9 = 19 ≡ 19 − 12 = 7 мы говорим, что проснулись в 7 часов. Для того, чтобы обозначить, что для нас 19 ≡ 7 мы использовали другой знак равенства ” ≡ ”. Пример 3.27. Поезд № 001М Владивосток-Москва отправляется каждый день в 04:00 (по Московскому времени). Время в пути 6 дней 2 часа. Во сколько поезд прибудет в Москву на Ярославский вокзал? Вычисляя, получим 04 + 6 · 24 + 2 = 150. Теперь, разделим 150 на 12 и найдем остаток 150 12 = 12 + 6 12 или 150 = 12 · 12 + 6. Т.е. поезд прибудет в Москву в 6 часов. (Мы пока не обсуждаем вопрос: утром или вечером?) Т.е. для определения данного времени нам понадобилось вычислить остаток от деления 150 на 12. Этот остаток и является ответом. Математически, данный факт записывается так 150 ≡ 6 (mod 12). Теперь, решения предыдущего примера записываются в виде: 11 + 2 = 13 ≡ 1 (mod 12), 10 + 9 = 19 ≡ 7 (mod 12). Кольцом называется множество элементов, с двумя бинарными операциями ("+"и ” × ”), которое является аддитивной группой, но мультипликативной полугруппой. Рассмотрим множество из трех целых чисел (0,1,2) и составим для него таблицу сложения и таблицу умножения по модулю 3: + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 × 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 Данное множество образует кольцо и обозначается как Z 3 3.6. Вычисления в полях Галуа 139 Для кольца Z 4 таблицы сложения и умножения по (mod 4) выглядят следующим образом + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 × 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 Заметим, что для элемента 2 не существует мультипликативного обратного. Т.е. в таблице умножения нет такого числа x которое дало бы 2 · x = 1. Для кольца Z 5 таблицы сложения и умножения по (mod 5) выглядят следующим образом + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 × 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 Из таблицы умножения для Z 5 можно видеть что для каждого ненулевого элемента существует обратный: 1 · 1 = 1, 2 · 3 = 1, 3 · 2 = 1, 4 · 4 = 1. Т.е. для 2 обратным элементом будет 3, для 3 - это 2, для 1 - это 1, а для 4 - это 4. Получается что в кольце Z 5 элементы (0,1,2,3,4) образуют группу как по сложению так и по умножению. Полем называется множество элементов, с двумя бинарными операциями ("+"и ” ×”), которое является группой как по сложению, так и по умножению (т.е. аддитивной и мультипликативной группой одновременно). Несложно проверить что все кольца Z p , для которых p является простым числом являются конечными полями. Для составления таблиц умножения в конечных полях и проведения в них арифметических операций часто пользуются таблицами индексов. Таблица индексов для Z 7 строиться следующим образом. Возьмем произвольное число (например 2) и будем искать остатки при делении его степени 2 n на 7: 2 0 ≡ 1 (mod 7), 2 1 ≡ 2 (mod 7), 2 2 ≡ 4 (mod 7), 2 3 = 8 ≡ 1 (mod 7).... Сведем ответы в таблицу n 0 1 2 3 4 5 6 2 n 1 2 4 1 2 4 1 Из таблиц видно, что значения остатков 2 n (mod 7) = (1, 2, 4) 140 Глава 3. Теория помехоустойчивого кодирования не принимают всех чисел кольца (1,2,3,4,5,6), т.е. 2 не является генератором Z 7 Теперь возьмем в качестве основания число 3: n 0 1 2 3 4 5 6 3 n 1 3 2 6 4 5 1 Из таблицы (экспонент) видно, что 3 n (mod 7) может принимать любое значение из набора (1,2,3,4,5,6), т.е. 3 является генератором Z 7 . Обратной к полученной таблице будет являтся таблица логарифмов (индексов): n 0 1 2 3 4 5 6 ind n 6 0 2 1 4 5 3 Пользуясь таблицей индексов и экспонент несложно производить некоторые арифметические операции 2 × 6 = 3 ind 2 × 3 ind 6 = 3 ind 2+ind 6 = 3 2+3 = 3 5 = 5, 3 × 5 = 3 ind 3 × 3 ind 5 = 3 ind 3+ind 5 = 3 1+5 = 3 6 = 3 0 = 1, 5 × 6 = 3 ind 5 × 3 ind 6 = 3 ind 5+ind 6 = 3 5+3 = 3 8 = 3 2 = 2. В последних двух выражения мы учли, что 6 ≡ 0 (mod 6) и 8 ≡ 2 (mod 6). Другими словами, умножение в кольце Z p чисел x и y производится по следующему правилу x × y = α ind x × α ind y = α (ind x+ind y) mod (p−1) Выпишем таблицы сложения и умножения для Z 7 : + 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 × 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 Кольцо Z 8 тоже можно превратить в поле, но для этого необходимо определить другие таблицы сложения и умножения, предварительно построив таблицу индексов. Такие поля (с собственными таблицами сложения и умножения) называются полями Галуа GF (p k ). 3.6. Вычисления в полях Галуа 141 F Для составления таблицы индексов поля GF (2 3 ) воспользуемся следующим замечательным трюком. Возьмем неприводимый полином 3 степени с коэффициентами из Z 2 : p(x) = x 3 + x + 1 и рассмотрим остатки от деления степеней x n на p(x): x 0 p(x) = 1 = 0001; x 1 p(x) = x = 0010 x 2 p(x) = x 2 = 0100; x 3 p(x) = x + 1 = 0011 x 4 p(x) = x 2 + x = 0110; x 5 p(x) = x 2 + x + 1 = 0111 x 6 p(x) = x 2 + 1 = 0101; x 7 p(x) = 1 = 0001 Учитывая, что в десятичной записи 001 = 1, 010 = 2, 011 = 3, 100 = 4, 101 = 5, 110 = 6, 111 = 7 из этих остатков составим таблицу индексов для GF (2 3 ) n 0 1 2 3 4 5 6 7 2 n 1 2 4 3 6 7 5 1 ind n 7 0 1 3 2 6 4 5 Теперь, пользуясь таблицей индексов несложно построить таблицу умножения для GF (2 3 ): ⊕ 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5 4 3 2 1 0 × 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 4 6 3 1 7 5 3 3 6 5 7 4 1 2 4 4 3 7 6 2 5 1 5 5 1 4 2 7 3 6 6 6 7 1 5 3 2 4 7 7 5 2 1 6 4 3 Заметим, что таблица сложения в данном случае тоже строиться по другому. В качестве операции сложения мы здесь используем оператор побитового сложения XOR - ” ⊕ ”. Например 2 + 3 = 010 ⊕ 011 = 001 = 1, 5 + 6 = 101 ⊕ 110 = 011 = 3. Поскольку и по сложению и по умножению наши элементы образуют группы то данное множество элементов можно назвать полем GF (2 3 ). 142 Глава 3. Теория помехоустойчивого кодирования F Аналогичным образом построим поле Галуа GF (2 4 ). Для этого возьмем неприводимый полином 4 степени с коэффициентами из Z 2 : p(x) = x 4 + x + 1 и рассмотрим остатки от деления степеней x n на p(x): h x 0 p i = 1 = 0001 h x 1 p i = x = 0010 h x 2 p i = x 2 = 0100 ... h x 4 p i = 1 + x = 0011 h x 5 p i = x + x 2 = 0110 h x 6 p i = x 2 + x 3 = 1100 ... h x 8 p i = 1 + x 2 = 0101 h x 9 p i = x + x 3 = 1010 h x 10 p i = 1 + x + x 2 = 0111 ... Учитывая, что в десятичной записи 0001 = 1, 0010 = 2, 0011 = 3, ..., 1101 = 13, 1110 = 14, 1111 = 15, из этих остатков составим таблицу индексов для GF (2 4 ) n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 n 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 1 ind n 15 0 1 4 2 8 5 10 3 14 9 7 6 13 11 12 Теперь, пользуясь таблицей индексов несложно построить таблицу умножения для GF (2 4 ): × 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 2 4 6 8 10 12 14 3 1 7 5 11 9 15 13 3 3 6 5 12 15 10 9 11 8 13 14 7 4 1 2 4 4 8 12 3 7 11 15 6 2 14 10 5 1 13 9 5 5 10 15 7 2 13 8 14 11 4 1 9 12 3 6 6 6 12 10 11 13 7 1 5 3 9 15 14 8 2 4 7 7 14 9 15 8 1 6 13 10 3 4 2 5 12 11 8 8 3 11 6 14 5 13 12 4 15 7 10 2 9 1 9 9 1 8 2 11 3 10 4 13 5 12 6 15 7 14 10 10 7 13 14 4 9 3 15 5 8 2 1 11 6 12 11 11 5 14 10 1 15 4 7 12 2 9 13 6 8 3 12 12 11 7 5 9 14 2 10 6 1 13 15 3 4 8 13 13 9 4 1 12 8 5 2 15 11 6 3 14 10 7 14 14 15 1 13 3 2 12 9 7 6 8 4 10 11 5 15 15 13 2 9 6 4 11 1 14 12 3 8 7 5 10 Сложение определяется как побитовая сумма по модулю 2 оператором XOR. В общем случае показанная схема позволяет для любого p k построить поле GF (p k ). 3.7. Коды БЧХ 143 3.7 Коды БЧХ Рассмотренные нами ранее полиномиальные коды для исправления ошибок требовали знания таблицы синдромов. Получается, что на приемнике информации должна быть выделена память для ее хранения. В противном случае для каждого блока принятой кодовой последоватеьльности необходимо рассчитывать синдромные остатки, а это опять задержки в передаче. Дальнейшей целью теории помехоустойчивого кодирования является построение алгоритмов, позволяющих определять ошибку пользуясь только принятой коддовой комбинацие. Очевидно что такие коды не обязаны быть совершенными, а главным параметром становиться простота их аппаратной реализации. Коды БЧХ 5 являются разновидностью полиномиальных и формируются по тому же принципу. Информационная последовательность a = (a k−1 a k−2 ...a 1 a 0 ) представляется в виде полинома m = a i x i = a k−1 x k−1 + a k−2 x k−2 + ... + a 1 x 1 + a 0 x 0 По формуле 2 r ≥ q X i=0 C i k+r определяется количество r проверочных символов, необходимых для исправления q ошибок. После чего смещенный полином x r m делится на проверочный p: x r m p = C + R p и формируется кодовая последовательность F = Cp = x r m p ⊕ R. Поскольку коды БЧХ формируются длля работы в полях GF (2 m ), то полиномы p = ψ i , i 6= 0 выбираются из множества x 2 m −1 − 1 = ψ 0 ψ 1 ψ 2 Например F GF (2 2 ) : x 3 − 1 = (1 + x)(1 + x + x 2 ) F GF (2 3 ) : x 7 − 1 = (1 + x)(1 + x + x 3 )(1 + x 2 + x 3 ) F GF (2 4 ) : x 15 − 1 = (1 + x)(1 + x + x 2 )(1 + x + x 4 )(1 + x 3 + x 4 )(1 + x + x 2 + x 3 + x 4 ) 5 Коды Боуза — Чоудхури — Хоквингема. 144 Глава 3. Теория помехоустойчивого кодирования F GF (2 5 ) : x 31 − 1 = (1 + x)(1 + x 2 + x 5 )(1 + x 3 + x 5 )(1 + x + x 2 + x 3 + x 5 ) × (1 + x + x 2 + x 4 + x 5 )(1 + x + x 3 + x 4 + x 5 )(1 + x 2 + x 3 + x 4 + x 5 ) Для создания проверочных полиномов можно брать произвольную комбинацию функций ψ, например p = ψ 1 ψ 3 ... (кроме ψ 0 = 1 + x). Заметим, что длина кода и количество исправляемых ошибок напрямую связаны с размерностью поля GF (2 m ). Обозначим через [n, k, q] код, длиной n с k информационными разрядами, исправляющий q ошибок. Тогда поле GF (2 m ) допускает построение следующих кодов БЧХ F GF (2 2 ) : [3, 1, 1] F GF (2 3 ) : [7, 4, 1], [7, 1, 2] F GF (2 4 ) : [15, 11, 1], [15, 7, 2], [15, 5, 3], [15, 1, 4] Существует множество различных алгоритмов декодирования кода БЧХ. Мы рассмотрим некоторые из них. 3.7.1 Прямой алгебраический метод PGZ Рассматриваемый декодер был впервые предложен В.В.Петерсоном в 1960 г. Допустим принятая кодовая комбинация A = (A n−1 A n−2 ...A 1 A 0 ) имеет вид F (x) = X A i x i = A n−1 x n−1 + A n−2 x n−2 + ... + A 1 x 1 + A 0 x 0 F Для исправления 1 ошибки нам достаточно подставить число 2 в принятую комбинацию F (2) = X A i 2 i = A n−1 2 n−1 + A n−2 2 n−2 + ... + A 1 2 1 + A 0 2 0 = 2 α Тогда α - степень искаженного разряда в полиноме кодовой комбинации. F Для исправления 2 ошибок нам необходимо рассчитать 4 значения S 1 = F (2 1 ) = X A i 2 i = A n−1 2 n−1 + A n−2 2 n−2 + ... + A 1 2 1 + A 0 2 0 S 2 = F (2 2 ) = X A i (2 2 ) i = A n−1 (2 2 ) n−1 + A n−2 (2 2 ) n−2 + ... + A 1 (2 2 ) 1 + A 0 (2 2 ) 0 S 3 = F (2 3 ) = X A i (2 3 ) i = A n−1 (2 3 ) n−1 + A n−2 (2 3 ) n−2 + ... + A 1 (2 3 ) 1 + A 0 (2 3 ) 0 S 4 = F (2 4 ) = X A i (2 4 ) i = A n−1 (2 4 ) n−1 + A n−2 (2 4 ) n−2 + ... + A 1 (2 4 ) 1 + A 0 (2 4 ) 0 После чего вычислить (σ 1 , σ 2 ) из выражения S 1 S 2 S 2 S 3 σ 2 σ 1 = S 3 S 4 и найти корни уравнения Σ(x) = 1 + σ 1 x + σ 2 x 2 = (1 + 2 α x)(1 + 2 β x). |