ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
Для исправления 3 ошибок нам необходимо рассчитать 6 значений S 1 = F (2 1 ) = X A i 2 i S 2 = F (2 2 ) = X A i (2 2 ) i S 3 = F (2 3 ) = X A i (2 3 ) i S 4 = F (2 4 ) = X A i (2 4 ) i S 5 = F (2 5 ) = X A i (2 5 ) i S 6 = F (2 6 ) = X A i (2 6 ) i После чего вычислить (σ 1 , σ 2 , σ 3 ) из выражения S 1 S 2 S 3 S 2 S 3 S 4 S 3 S 4 S 5 σ 3 σ 2 σ 1 = S 4 S 5 S 6 и найти корни уравнения Σ(x) = 1 + σ 1 x + σ 2 x 2 + σ 3 x 3 = (1 + 2 α x)(1 + 2 β x)(1 + 2 γ x). Тогда (α, β, γ) являются степенями искаженных разрядов в полиноме кодовой комбинации. F В самом общем случае для исправления q ошибок нам необходимо рассчитать 2q значений S k = F (2 k ) = X A i (2 k ) i После чего вычислить (σ 1 , σ 2 , ..., σ q ) из выражения S 1 S 2 S 3 S q S 2 S 3 S 4 S q+1 S q S q+1 S q+2 ... S 2q−1 σ q σ q−1 σ 2 σ 1 = S q+1 S q+2 S 2q−1 S 2q и найти корни уравнения 1 + σ 1 x + σ 2 x 2 + σ 3 x 3 + ... + σ q x q = (1 + 2 α 1 x)(1 + 2 α 2 x)...(1 + 2 α q x) или Σ(x) = q X j=0 σ j x j = q Y j=0 (1 + 2 α j x) Тогда (α 1 , α 2 , ..., α q ) являются степенями искаженных разрядов в полиноме кодовой комбинации. 3.7.2 Коды БЧХ над GF (2 3 ) Пример 3.28. Рассмотрим построение кода БЧХ в GF (2 3 ) исправляющего 1 ошибку при передаче информационной последовательности a = (1001). 146 Глава 3. Теория помехоустойчивого кодирования Решение. Пользуясь алгоритмами построения полиномиального кода из выражения 2 r ≥ k + r + 1 находим r = 3. Информационная последовательность a = (1001) представляется в виде m(x) = x 3 · 1 + x 2 · 0 + x · 0 + 1 · 1 = x 3 + 1. Поскольку r = 3, то умножаем Q(x) = x r m = x 3 m = x 3 (x 3 + x 2 + x + 1) = x 6 + x 5 + x 4 + x 3 = 1001000. Поскольку таблица индексов для GF (2 3 ) строилась относительно полинома p = x 3 + x + 1, то в разложении x 7 − 1 = ψ 0 ψ 1 ψ 2 = (1 + x)(1 + x + x 3 )(1 + x 2 + x 3 ) возьмем p = ψ 1 . Делим m = x r Q на образующий полином p x 3 m p = C + R p или x 6 + x 3 x 3 + x + 1 = (x 3 + x) + x 2 + x x 3 + x + 1 окуда получим R = x 2 + x = (110). Поскольку Q(x) = x 6 + x 5 + x 4 + x 3 = 1001000 то передаваемая комбинация F есть прямая конкатенация m ⊕ R: Q = 1001000 R = 110 F = 1001110 Таким образом, передаваемая кодовая комбинация имеет вид F = (1001110). N Допустим во время передачи по каналу информации в F возникла ошибка в 3 символе слева. F = (1001110) → F = (1011110) Опишем алгоритм определения и исправления ошибки кода БЧХ [7, 4]. 3.7. Коды БЧХ 147 Пример 3.29. Обнаружить и исправить ошибку в кодовой БЧХ последовательности F = (1011110) над GF (2 3 ). Решение. Перепишем принятую кодовую комбинацию F = (1011110) в полиномиальном виде F (x) = X F i x i = x 6 + x 4 + x 3 + x 2 + x. Для исправления 1 ошибки нам достаточно подставить число 2 в принятую комбинацию F (2) = X F i 2 i = 2 6 + 2 4 + 2 3 + 2 2 + 2 = 5 + 6 + 3 + 4 + 2 = 6 = 2 4 Здесь степень 2 k вычислялась по таблице индексов поля GF (2 3 ), а в качестве сложения использовалась операция XOR (или см. таблицу сложения для GF (2 3 )). Поскольку 2 α = 2 4 , то α = 4 степень искаженного разряда в полиноме кодовой комбинации: F = (1011110) → F = (1001110). Т.к. код БЧХ является систематическим, то для выделения информационной последовательности нам достаточно вычеркнуть r = 3 последних разряда кодовой комбинации a = (1001). N Задача 3.18. На приемнике была получена кодовая последовательность БЧХ [7,4] над GF (2 3 ). Восстановить исходное сообщение. N F N F N F 1 1110001 11 0101001 21 1001001 2 0111010 12 1101010 22 0001010 3 1010011 13 0100011 23 1100011 4 1011100 14 0001100 24 1101100 5 0100001 15 1101110 25 0011111 6 0100111 16 1110110 26 0100111 7 0100100 17 1000110 27 0001011 8 1100111 18 0100110 28 0001101 9 1100100 19 1001111 29 0001110 10 1100010 20 0101111 30 1110010 Следующий пример преследует исключительно методическую цель, поскольку применение данного алгоритма на практике не рационально. Мы построим код БЧХ в GF (8) исправляющий 2 ошибки. 148 Глава 3. Теория помехоустойчивого кодирования Пример 3.30. Рассмотрим построение кода БЧХ в GF (2 3 ) исправляющего 2 ошибки. Решение. Для исправления 1 ошибки мы пользовались полиномом p = ψ 1 Для исправления 2 ошибок нам необходимо взять 2 функции ψ. Тогда проверочный полином будет выглядеть так p = ψ 1 ψ 2 = (1 + x + x 3 )(1 + x 2 + x 3 ) = 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 Т.е. нам необходимо взять r = 6 проверочных символов для построения кода БЧХ [7, 1] исправляющего 2 ошибки 6 Допустим информационная последовательность имеет вид a = (1) представляется в виде m(x) = 1. Поскольку r = 6, то умножаем Q(x) = x r m = x 6 · 1 = x 6 = 1000000. Делим Q = x r m на проверочный полином p x 6 m p = C + R p или x 6 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 = 1 + 1 + x + x 2 + x 3 + x 4 + x 5 1 + x + x 2 + x 3 + x 4 + x 5 + x 6 окуда получим R = 1 + x + x 2 + x 3 + x 4 + x 5 . Поскольку Q(x) = x 6 = 1000000 то передаваемая комбинация F есть прямая конкатенация m ⊕ R: Q = 1000000 R = 111111 F = 1111111 Таким образом, передаваемая кодовая комбинация имеет вид F = (1111111). N Допустим во время передачи по каналу информации в F возникло две ошибки во 2 и 5 символе слева. F = (1111111) → F = (1011011) Опишем алгоритм определения и исправления ошибки кода БЧХ [7, 1]. 6 Заметим, что повторный код [5, 1] : 1 → 11111, исправляющий 2 ошибки имеет длину n = 5, а повторный код длины n = 7, [n, k] = [7, 1] исправляет 3 ошибки. Т.е. в данном примере код БЧХ уступает по скорости 1/7 < 1/5 даже простейшему повторному. 3.7. Коды БЧХ 149 Пример 3.31. Обнаружить и исправить ошибки в БЧХ кодовой последовательности A = (1011011) над GF (2 3 ). Решение. Перепишем принятую кодовую комбинацию A = (1011011) в полиномиальном виде F (x) = X A i x i = x 6 + x 4 + x 3 + x + 1. Для исправления двух ошибок нам необходимо рассчитать 4 значения S 1 = F (2 1 ) = X A i 2 i = 2 6 + 2 4 + 2 3 + 2 + 1 = 5 + 6 + 3 + 2 + 1 = 3 S 2 = F (2 2 ) = X A i (2 2 ) i = 2 12 + 2 8 + 2 6 + 2 2 + 1 = 7 + 2 + 5 + 4 + 1 = 5 S 3 = F (2 3 ) = X A i (2 3 ) i = x 18 + 2 12 + x 9 + 2 3 + 1 = 6 + 7 + 4 + 3 + 1 = 7 S 4 = F (2 4 ) = X A i (2 4 ) i = x 24 + x 16 + x 12 + 2 4 + 1 = 3 + 4 + 7 + 6 + 1 = 7 Те читатели, которые захотят рассчитать предыдущие суммы устно (без компьютера) должны помнить, что в GF (2 3 ) возведение в степень имеет свойства 2 k = 2 k+7 , т.е. 2 18 = 2 4 = 6, 2 24 = 2 3 = 3, 2 16 = 2 2 = 4, и т.д. Теперь вычислим (σ 1 , σ 2 ) из выражения S 1 S 2 S 2 S 3 σ 2 σ 1 = S 3 S 4 , т.е. 3 5 5 7 σ 2 σ 1 = 7 7 По методу Крамера найдем ∆ = 3 5 5 7 = 3 · 7 − 5 · 5 = 2 + 7 = 5 ∆ 2 = 7 5 7 7 = 7 · 7 − 7 · 5 = 3 + 6 = 5; ∆ 1 = 3 7 5 7 = 3 · 7 − 5 · 7 = 2 + 6 = 4 По таблице умножения в GF (2 3 ) получим ∆ −1 = 5 −1 = 2. Тогда σ 1 = ∆ 1 ∆ = ∆ 1 · ∆ −1 = 4 · 2 = 3; σ 2 = ∆ 2 ∆ = ∆ 2 · ∆ −1 = 5 · 2 = 1 Теперь подставим полученные значения (σ 1 , σ 2 ) в уравнение Σ(x) = 1 + σ 1 x + σ 2 x 2 = 1 + 3x + x 2 150 Глава 3. Теория помехоустойчивого кодирования Для решения данного уравнения воспользуемся формулами Виета x 1 + x 2 = σ 1 x 1 · x 2 = σ 2 или x 1 + x 2 = 3 x 1 · x 2 = 1 По таблицам сложения и умножения для GF (2 3 ) находим x 1 = 4, x 2 = 7, тогда Σ(x) = 1 + 3x + x 2 = (1 + 4x)(1 + 7x) = (1 + 2 2 x)(1 + 2 5 x). Т.е. ошибки в коэффициентах при степенях x 2 и x 5 полинома F (x). Меняя значения разрядов на противоположные получим F = (1011011) → F = (1111111) - исправленную кодовую комбинацию. N Задача 3.19. На приемнике была получена кодовая последовательность БЧХ [7,1] над GF (2 3 ). Восстановить исходное сообщение. N F N F N F N F N F N F 1 0101111 6 1100111 11 0101111 16 1111100 21 1011110 26 1011110 2 0110111 7 1101011 12 0110111 17 1111010 22 1011101 27 1011011 3 0111011 8 1101101 13 0111011 18 1111001 23 1011011 28 1001111 4 0111101 9 1101110 14 0111101 19 1110110 24 1010111 29 1110101 5 0111110 10 1110011 15 0111110 20 1010111 25 1011101 30 1001111 3.7.3 Коды БЧХ над GF (2 4 ) Пример 3.32. Рассмотрим построение кода БЧХ в GF (2 4 ) исправляющего 1 ошибку при передаче информационной последовательности a = (11100011100). Решение. Пользуясь алгоритмами построения полиномиального кода из выражения 2 r ≥ k + r + 1 = 11 + r + 1 = 12 + r находим r = 4. Информационная последовательность a = (11100011100) представляется в виде m(x) = x 10 + x 9 + x 8 + x 4 + x 3 + x 2 Поскольку r = 4, то умножаем m на x 4 : Q(x) = x r m = x 4 m = x 4 (x 10 + x 9 + x 8 + x 4 + x 3 + x 2 ) = x 14 + x 13 + x 12 + x 8 + x 7 + x 6 = 111000111000000. 3.7. Коды БЧХ 151 Поскольку таблица индексов для GF (2 4 ) строилась относительно полинома p = x 4 + x + 1, то в разложении x 15 − 1 = ψ 0 ψ 1 ψ 2 ψ 3 ψ 4 = (1 + x)(1 + x + x 2 )(1 + x + x 4 )(1 + x 3 + x 4 )(1 + x + x 2 + x 3 + x 4 ) возьмем p = ψ 2 . Делим Q = x r m на проверочный полином p x 4 m p = C + R p или x 14 + x 13 + x 12 + x 8 + x 7 + x 6 x 4 + x + 1 = 1 + x + x 2 + x 4 + x 7 + x 8 + x 9 + 1 + x 3 x 4 + x + 1 окуда получим R = x 3 + 1 = (1001). Поскольку Q(x) = x 14 + x 13 + x 12 + x 8 + x 7 + x 6 = 111000111000000 то передаваемая комбинация F есть прямая конкатенация Q ⊕ R: Q = 111000111000000 R = 1001 F = 111000111001001 Таким образом, передаваемая кодовая комбинация имеет вид F = (111000111001001).N Допустим во время передачи по каналу информации в F возникла ошибка в 5 символе слева. F = (111000111001001) → F = (111010111001001) Опишем алгоритм определения и исправления ошибки кода БЧХ [15, 11]. Пример 3.33. Обнаружить и исправить ошибку в кодовой БЧХ последовательности F = (111010111001001) над GF (2 4 ). Решение. Перепишем принятую кодовую комбинацию F = (111010111001001) в полиномиальном виде F (x) = X F i x i = x 14 + x 13 + x 12 + x 10 + x 8 + x 7 + x 6 + x 3 + 1. Для исправления 1 ошибки нам достаточно подставить число 2 в принятую комбинацию F (2) = X F i 2 i = 2 14 + 2 13 + 2 12 + 2 10 + 2 8 + 2 7 + 2 6 + 2 3 + 1 = 9 + 13 + 15 + 7 + 5 + 11 + 12 + 8 + 1 = 7 = 2 10 152 Глава 3. Теория помехоустойчивого кодирования Здесь степень 2 k вычислялась по таблице индексов поля GF (2 4 ), а в качестве сложения использовалась операция XOR (или см. таблицу сложения для GF (2 4 )). Поскольку 2 α = 2 10 , то α = 10 степень искаженного разряда в полиноме кодовой комбинации: F = (111010111001001) → F = (111000111001001) Т.к. код БЧХ является систематическим, то для выделения информационной последовательности нам достаточно вычеркнуть r = 4 последних разряда кодовой комбинации a = (11100011100). N Задача 3.20. На приемнике была получена кодовая последовательность БЧХ [15, 11] над GF (2 4 ). Восстановить исходное сообщение. N F N F N F 1 111100001111110 11 110011001100011 21 101010101011001 2 111100001111000 12 110011001100001 22 101010101011111 3 111100001110100 13 110011001100111 23 101010101010011 4 111100001101100 14 110011001101011 24 101010101001011 5 111100001011100 15 110011001110011 25 101010101111011 6 111100000111100 16 110011001000011 26 101010100011011 7 111100011111100 17 110011000100011 27 101010111011011 8 111100101111100 18 110011011100011 28 101010001011011 9 111101001111100 19 110011101100011 29 101011101011011 10 111110001111100 20 110010001100011 30 101000101011011 Пример 3.34. Рассмотрим построение кода БЧХ в GF (2 4 ) исправляющего 2 ошибки. Решение. Пользуясь алгоритмами построения полиномиального кода из выражения 2 r ≥ C 1 15 + C 2 15 = 15 + 105 = 120 находим r = 7. Т.е. нам необходимо не менее 7 проверочных разрядов. Тогда из разложения x 15 − 1 = ψ 0 ψ 1 ψ 2 ψ 3 ψ 4 = (1 + x)(1 + x + x 2 )(1 + x + x 4 )(1 + x 3 + x 4 )(1 + x + x 2 + x 3 + x 4 ) возьмем ψ 2 - как образующий поля GF (2 4 ) и ψ 4 : p = ψ 2 ψ 4 = (1 + x + x 4 )(1 + x + x 2 + x 3 + x 4 ) = 1 + x 4 + x 6 + x 7 + x 8 мы получим r = 8. Таким образом БЧХ код в GF (2 4 ), исправляющий 2 ошибки будет иметь вид [n, k] = [15, 7]. Допустим информационная последовательность имеет вид a = (1110001) и представляется в виде m(x) = 1 + x 4 + x 5 + x 6 3.7. Коды БЧХ 153 Поскольку r = 8, то умножаем Q(x) = x r m = x 8 · (1 + x 4 + x 5 + x 6 ) = x 14 + x 13 + x 12 + x 8 Делим m = x r Q на проверочный полином p x 8 m p = C + R p или x 14 + x 13 + x 12 + x 8 1 + x 4 + x 6 + x 7 + x 8 = 1 + x + x 2 + x 6 + 1 + x + x 2 + x 4 + x 5 + x 6 1 + x 4 + x 6 + x 7 + x 8 окуда получим R = 1 + x + x 2 + x 4 + x 5 + x 6 = 01110111. Поскольку Q(x) = x 14 + x 13 + x 12 + x 8 = 111000100000000 то передаваемая комбинация F есть прямая конкатенация Q ⊕ R: Q = 111000100000000 R = 01110111 F = 111000101110111 Таким образом, передаваемая кодовая комбинация имеет вид F = (111000101110111).N Допустим во время передачи по каналу информации в F возникло две ошибки в 3 и 8 символе слева. F = (111000101110111) → F = (110000111110111) Опишем алгоритм определения и исправления ошибки кода БЧХ [15, 7]. Пример 3.35. Обнаружить и исправить ошибки в БЧХ кодовой последовательности F = (110000111110111) над GF (2 4 ). Решение. Перепишем принятую кодовую комбинацию F = (110000111110111) в полиномиальном виде F (x) = X F i x i = x 14 + x 13 + x 8 + x 7 + x 6 + x 5 + x 4 + x 2 + x + 1. Для исправления двух ошибок нам необходимо рассчитать 4 значения S 1 = F (2 1 ) = X F i 2 i = 2 14 + 2 13 + 2 8 + 2 7 + 2 6 + 2 5 + 2 4 + 2 2 + 2 + 1 = 4 S 2 = F (2 2 ) = X F i 4 i = 4 14 + 4 13 + 4 8 + 4 7 + 4 6 + 4 5 + 4 4 + 4 2 + 4 + 1 = 3 S 3 = F (2 3 ) = X F i 8 i = 8 14 + 8 13 + 8 8 + 8 7 + 8 6 + 8 5 + 8 4 + 8 2 + 8 + 1 = 0 S 4 = F (2 4 ) = X F i 3 i = 3 14 + 3 13 + 3 8 + 3 7 + 3 6 + 3 5 + 3 4 + 3 2 + 3 + 1 = 5 154 Глава 3. Теория помехоустойчивого кодирования Те читатели, которые захотят рассчитать предыдущие суммы устно (без компьютера) должны помнить, что в GF (2 4 ) возведение в степень имеет свойства 2 k = 2 k+15 , т.е. 2 18 = 2 3 = 8, 2 24 = 2 9 = 10, 2 16 = 2 1 = 1, и т.д. Теперь вычислим (σ 1 , σ 2 ) из выражения S 1 S 2 S 2 S 3 σ 2 σ 1 = S 3 S 4 , т.е. 4 3 3 0 σ 2 σ 1 = 0 5 По методу Крамера найдем ∆ = 4 3 3 0 = 4 · 0 − 3 · 3 = 0 + 5 = 5 ∆ 2 = 0 3 5 0 = 0 · 0 − 5 · 3 = 0 + 15 = 15; ∆ 1 = 4 0 3 5 = 4 · 5 − 3 · 0 = 7 + 0 = 7. По таблице умножения в GF (2 4 ) получим ∆ −1 = 5 −1 = 11. Тогда σ 1 = ∆ 1 ∆ = ∆ 1 · ∆ −1 = 7 · 11 = 4; σ 2 = ∆ 2 ∆ = ∆ 2 · ∆ −1 = 15 · 11 = 3. Теперь подставим полученные значения (σ 1 , σ 2 ) в уравнение Σ(x) = 1 + σ 1 x + σ 2 x 2 = 1 + 4x + 3x 2 = (1 + 11x)(1 + 15x) = (1 + 2 7 x)(1 + 2 12 x). Тогда α = 7 и β = 12 являются степенями искаженных разрядов в полиноме кодовой комбинации. Меняя значения разрядов на противоположные получим F = (110000111110111) → F = (111000101110111) - исправленную кодовую комбинацию. N Задача 3.21. На приемнике была получена кодовая последовательность БЧХ [15, 7] над GF (2 4 ). Восстановить исходное сообщение. N F N F N F 1 111110111100101 11 110110111111000 21 101001100111110 2 111000111100101 12 111010111111000 22 100101100111110 3 111010011100101 13 111100111111000 23 100011100111110 4 111010101100101 14 111111111111000 24 100000100111110 5 111010110100101 15 111110011111000 25 100001000111110 6 111010111000101 16 111110101111000 26 100001110111110 7 101111111100101 17 111110110111000 27 100001101111110 8 101110011100101 18 111110111011000 28 100001100011110 9 101110101100101 19 111110111101000 29 100001100101110 10 101110110100101 20 111110111110000 30 100001100110110 3.7. Коды БЧХ 155 Пример 3.36. Рассмотрим построение кода БЧХ [15, 5] в GF (2 4 ) исправляющего 3 ошибки. Решение. Пользуясь алгоритмами построения полиномиального кода из выражения 2 r ≥ C 1 15 + C 2 15 + C 3 15 = 15 + 105 + 455 = 575 находим r = 10. Т.е. нам необходимо не менее 10 проверочных разрядов. Тогда из разложения x 15 − 1 = ψ 0 ψ 1 ψ 2 ψ 3 ψ 4 = (1 + x)(1 + x + x 2 )(1 + x + x 4 )(1 + x 3 + x 4 )(1 + x + x 2 + x 3 + x 4 ) возьмем ψ 2 - как образующий поля GF (2 4 ), ψ 4 и ψ 1 : p = ψ 1 ψ 2 ψ 4 = (1 + x + x 2 )(1 + x + x 4 )(1 + x + x 2 + x 3 + x 4 ) = 1 + x + x 2 + x 4 + x 5 + x 8 + x 10 Таким образом БЧХ код в GF (2 4 ), исправляющий 3 ошибки будет иметь вид [n, k] = [15, 5]. Допустим информационная последовательность имеет вид a = (11110) и представляется в виде m(x) = x + x 2 + x 3 + x 4 Поскольку r = 10, то умножаем Q(x) = x r m = x 10 · (x + x 2 + x 3 + x 4 ) = x 14 + x 13 + x 12 + x 11 Делим Q = x r m на проверочный полином p x 10 m p = C + R p или x 14 + x 13 + x 12 + x 11 1 + x + x 2 + x 4 + x 5 + x 8 + x 10 = x 3 + x 4 + x 3 + x 6 + x 7 + x 9 1 + x + x 2 + x 4 + x 5 + x 8 + x 10 окуда получим R = x 3 + x 6 + x 7 + x 9 = 1011001000. Поскольку Q(x) = x 14 + x 13 + x 12 + x 8 = 111100000000000 то передаваемая комбинация F есть прямая конкатенация Q ⊕ R: Q = 111100000000000 R = 1011001000 F = 111101011001000 Таким образом, передаваемая кодовая комбинация имеет вид F = (111101011001000).N Допустим во время передачи по каналу информации в F возникло три ошибки в 2, 5 и 11 символе слева. F = (111101011001000) → F = (101111011011000) 156 Глава 3. Теория помехоустойчивого кодирования Опишем алгоритм определения и исправления ошибки кода БЧХ [15, 5]. Пример 3.37. Обнаружить и исправить ошибки в БЧХ [15, 5] кодовой последовательности F = (101111011011000) над GF (2 4 ). Решение. Перепишем принятую кодовую комбинацию F = (101111011011000) в полиномиальном виде F (x) = X F i x i = x 14 + x 12 + x 11 + x 10 + x 9 + x 7 + x 6 + x 4 + x 3 Для исправления двух ошибок нам необходимо рассчитать 6 значений S 1 = F (2 1 ) = X F i 2 i = 9 S 2 = F (2 2 ) = X F i 4 i = 13 S 3 = F (2 3 ) = X F i 8 i = 4 S 4 = F (2 4 ) = X F i 3 i = 14 S 5 = F (2 5 ) = X F i 6 i = 6 S 6 = F (2 6 ) = X F i 12 i = 3 Теперь вычислим (σ 1 , σ 2 , σ 3 ) из выражения S 1 S 2 S 3 S 2 S 3 S 4 S 3 S 4 S 5 σ 3 σ 2 σ 1 = S 4 S 5 S 6 , т.е. 9 13 4 13 4 14 4 14 6 σ 3 σ 2 σ 1 = 14 6 3 По методу Крамера найдем ∆ = 9 13 4 13 4 14 4 14 6 = 14 ∆ 3 = 14 13 4 6 4 14 3 14 6 = 5 ∆ 2 = 9 14 4 13 6 14 4 3 6 = 9 ∆ 1 = 9 13 14 13 4 6 4 14 3 = 7 По таблице умножения в GF (2 4 ) получим ∆ −1 = 14 −1 = 3. Тогда σ 1 = ∆ 1 ∆ = ∆ 1 · ∆ −1 = 7 · 3 = 9 σ 2 = ∆ 1 ∆ = ∆ 2 · ∆ −1 = 9 · 3 = 8 σ 1 = ∆ 1 ∆ = ∆ 1 · ∆ −1 = 5 · 3 = 15 Теперь подставим полученные значения (σ 1 , σ 2 , σ 3 ) в уравнение Σ(x) = 1 + σ 1 x + σ 2 x 2 + σ 3 x 3 = 1 + 9x + 8x 2 + 15x 3 = (1 + 3x)(1 + 7x)(1 + 13x) = (1 + 2 4 x)(1 + 2 10 x)(1 + 2 13 x). 3.7. Коды БЧХ 157 Тогда α 1 = 4, α 2 = 10, α 3 = 13 являются степенями искаженных разрядов в полиноме кодовой комбинации. Меняя значения разрядов на противоположные получим F = (101111011011000) → F = (111101011001000) - исправленную кодовую комбинацию. N Задача 3.22. На приемнике была получена кодовая последовательность БЧХ [15, 5] над GF (2 4 ). Восстановить исходное сообщение. N F N F N F 1 110011110101111 11 111011001000001 21 100111000010111 2 110011110101001 12 111011001001101 22 100111000010001 3 110011110100101 13 111011001010101 23 100111000011101 4 110011110111101 14 111011001100101 24 100111000000101 5 110011110001101 15 111011000000101 25 100111000110101 6 110011111101101 16 111011011000101 26 100111001010101 7 110011100101101 17 111011101000101 27 100111010010101 8 110011010101101 18 111010001000101 28 100111100010101 9 110010110101101 19 111001001000101 29 100110000010101 10 110001110101101 20 111111001000101 30 100101000010101 Для кодов исправляющих 1-2 ошибки можно предложить еще один эффективный метод декодирования. Допустим вектор F содержит две ошибки e(x) = x α +x β , тогда S 1 = 2 α + 2 β S 3 = 2 3α + 2 3β Если η 1 = 2 α , η 2 = 2 β - локаторы ошибок, то S 1 = η 1 + η 2 S 3 = η 3 1 + η 3 2 поэтому S 3 = S 3 1 + S 2 1 η 1 + S 1 η 2 1 ⇒ 1 + S 1 η −1 1 + S 2 1 + S 3 S −1 1 η −2 1 = 0. F Если имеется 2 ошибки, то полином локаторов имеет вид 1 + S 1 x + S 2 1 + S 3 S −1 1 x 2 = 0 F Если имеется 1 ошибка, то S 3 1 + S 3 = 0 и полином локаторов имеет вид 1 + S 1 x = 0 F Если ошибок нет, то S 1 = S 3 = 0. 158 Глава 3. Теория помехоустойчивого кодирования В заключение параграфа выпишем коэффициенты полинома локатора Σ(x) = 1 + σ 1 x + σ 2 x 2 + ... + σ k x k = 0 для кода, исправляющего k<6 ошибок: F Коррекция 1 ошибки σ 1 = S 1 F Коррекция 2 ошибок σ 1 = S 1 σ 2 = S 3 + S 3 1 S 1 F Коррекция 3 ошибок σ 1 = S 1 σ 2 = S 2 1 S 3 + S 5 S 3 + S 3 1 , σ 3 = S 3 1 + S 3 + S 1 σ 2 F Коррекция 4 ошибок σ 1 = S 1 σ 2 = S 1 (S 7 + S 7 1 ) + S 3 (S 5 1 + S 5 ) S 3 (S 3 1 + S 3 ) + S 1 (S 5 1 + S 5 ) , σ 3 = S 3 1 + S 3 + S 1 σ 2 , σ 4 = S 5 + S 2 1 S 3 + (S 3 1 + S 3 )σ 2 S 1 F Коррекция 5 ошибок σ 1 = S 1 σ 2 = (S 3 1 +S 3 )[S 9 1 +S 9 +S 4 1 (S 5 +S 3 1 S 3 )+S 2 3 (S 3 1 +S 3 )]+(S 5 1 +S 5 )(S 7 1 +S 7 )+S 1 (S 2 3 +S 1 S 5 ) (S 3 1 +S 3 )[S 7 +S 7 1 +S 1 S 3 (S 3 1 +S 3 )]+(S 5 +S 2 1 S 3 )(S 5 1 +S 5 ) σ 3 = S 3 1 + S 3 + S 1 σ 2 σ 4 = S 9 1 + S 9 + S 2 3 (S 3 1 + S 3 ) + S 4 1 (S 5 + S 2 1 S 3 ) + σ 2 [S 7 + S 7 1 + S 1 S 3 (S 3 1 + S 3 )] S 5 1 + S 5 σ 5 = S 5 + S 2 1 S 3 + S 1 S 4 + σ 2 (S 3 1 + S 3 ) Пример 3.38. Обнаружить и исправить ошибки в БЧХ [7, 1] кодовой последовательности F = (0111111) над GF (2 3 ). Решение. Вычислим вектор синдромов: S = (S 1 , S 2 , S 3 , S 4 ) = (5, 7, 6, 3). Поскольку код БЧХ [7, 1] может исправить до двух ошибок, то σ 1 = S 1 , σ 2 = S 3 + S 3 1 S 1 и полином локаторов имеет вид Σ(x) = 1 + σ 1 x + σ 2 x 2 = 1 + S 1 x + S 3 + S 3 1 S 1 x 2 = 1 + 5x + 6 + 5 3 5 x 2 = 1 + 5x = 1 + 2 6 x. Т.е. ошибка в 6 степени. N 3.7. Коды БЧХ 159 3.7.4 Расширенный алгоритм Евклида Расширенный алгоритм евклида для определения коэффициентов Безу также является итеррационным и требует вычисления остатков полиномов. Нам необходимо найти такие полиномы (Y, Σ), которые удовлетворяют равенству Безу x r Y + SΣ = 1. Для этого мы записываем полином x r через S = P S k x k в виде x r = S · q 0 + r 1 После чего расширенный алгоритм Евклида (относительно S) дает x r = S · q 0 + r 1 0 − 1 · q 0 = −q 0 σ 1 = q 0 S = r 1 · q 1 + r 2 1 + q 0 · q 1 = 1 + q 0 q 1 σ 2 = σ 1 q 1 + 1 r 1 = r 2 · q 2 + r 3 −q 0 − (1 + q 0 q 1 ) · q 2 = −(q 0 + (1 + q 0 q 1 )q 2 ) σ 3 = σ 2 q 2 + σ 1 r 2 = r 3 · q 3 + r 5 (1 + q 0 q 1 ) + (q 0 + (1 + q 0 q 1 )q 2 ) · q 2 = σ 4 σ 4 = σ 3 q 3 + σ 2 Этот коэффициент Безу и является полиномом локаторов: σ n+1 = σ n q n + σ n−1 , σ 0 = 1, σ −1 = 0. F 1 ошибка σ 1 = σ 0 q 0 = q 0 Т.к. x r = x 3 и S(x) = 1 + S 1 x + S 2 x 2 = 1 + S 1 x + S 2 1 x 2 найдем q 0 x r = S · q 0 + r 1 x 3 = (1 + S 1 x + S 2 1 x 2 ) 1 + S 1 x S 3 1 + 1 S 3 1 т.е. q 0 = 1+S 1 x S 3 1 тогда Σ = 1 + S 1 x F 2 ошибки σ 2 = σ 1 q 1 + σ 0 = q 0 q 1 + 1 нам необходимо найти q 0 и q 1 из последовательности выражений x r = S · q 0 + r 1 S = r 1 · q 1 + r 2 Т.к. x r = x 5 и S(x) = 1 + S 1 x + S 2 1 x 2 + S 3 x 3 + S 4 1 x 2 160 Глава 3. Теория помехоустойчивого кодирования получим x 5 = (1 + S 1 x + S 2 1 x 2 + S 3 x 3 + S 4 1 x 2 ) S 3 + S 4 1 x S 1 + S 3 + (S 1 S 3 + S 4 1 )x + (S 5 1 + S 2 1 S 3 )x + (S 5 1 + S 2 1 S 3 )x 2 S 1 т.е. q 0 = S 3 +S 4 1 x S 1 Далее 1 + xS 1 + x 2 S 2 1 + x 3 S 3 + x 4 S 4 1 = = S 3 + x (S 4 1 + S 1 S 3 ) + x 2 (S 5 1 + S 2 1 S 3 ) + x 3 (S 6 1 + S 2 3 ) S 8 1 × × S 14 1 + xS 15 1 + S 11 1 S 3 + xS 12 1 S 3 + S 8 1 s 2 3 S 9 1 + S 6 1 S 3 + S 3 1 S 2 3 + S 3 3 + + S 9 1 + x 2 S 11 1 + x 2 S 8 1 S 3 S 9 1 + S 6 1 S 3 + S 3 1 S 2 3 + S 3 3 т.е. q 1 = S 14 1 + xS 15 1 + S 11 1 S 3 + xS 12 1 S 3 + S 8 1 S 2 3 S 9 1 + S 6 1 S 3 + S 3 1 S 2 3 + S 3 3 тогда 1 + q 0 q 1 = 1 + S 3 + S 4 1 x S 1 S 14 1 + xS 15 1 + S 11 1 S 3 + xS 12 1 S 3 + S 8 1 S 2 3 S 9 1 + S 6 1 S 3 + S 3 1 S 2 3 + S 3 3 = S 2 1 (1 + S 1 x + x 2 (S 2 1 + S −1 1 S 3 )) S 9 1 + S 6 1 S 3 + S 3 1 S 2 3 + S 3 3 и Σ 2 = 1 + S 1 x + (S 2 1 + S −1 1 S 3 )x 2 F 3 ошибки Σ 3 = σ 2 q 2 + σ 1 = q 0 q 1 q 2 + q 0 + q 2 F 4 ошибки Σ 4 = σ 3 q 3 + σ 2 = q 0 q 1 q 2 q 3 + q 0 q 3 + q 2 q 3 + q 1 q 0 + 1 3.8. Совершенные недвоичные коды 161 3.8 Совершенные недвоичные коды 3.8.1 Введение Пусть q 6= 2 - степень простого числа. Известно [1], что при k 6= 0, n не существует совершенного кода [n, k, d] q , отличного от n = q m − 1 q − 1 , n − m, 3 q и [11, 6, 5] 3 Все совершенные двоичные коды могут быть построены методом Хэмминга [2]. Для совершенных недвоичных кодов над Z p математических проблем не возникает. Построение же кодов над GF (p m ) требует разработки новых методов. Это связано с тем, что кольцо Z p m не является полем. Так в [3] для кодирования в GF (2 m ) предлагается использовать дискретное преобразование Фурье. Для построения кода Рида-Соломона в [4] вводятся специфические законы сложения и умножения. Однако полученные коды имеют, соответственно, параметры [n, k] = [2 m , 2 m−1 ] и [n, k] = [2 m − 1, 2 m − 3] и не являются совершеннными. Несмотря на сомнительную практическую значимость, работы по созданию новых кодов над полями малых размерностей ведутся достаточно интенсивно [5], поскольку дают взможность отработать новые алгоритмы и методы. Аналогично, одной из основных причин пристального внимания к совершеннным кодам является то, что они нередко становятся базисными для построения других кодов. Удачно построенный алгоритм позволяет оставаться вблизи границы Синглтона даже при значительном расширении и изменении совершенного кода. В настоящей работе предлагается простой алгоритм построения совершенного кода над GF (2 m ). 3.8.2 Совершенный код в GF (2 2 ) Построим таблицу умножения для элементов из поля Галуа GF (2 2 ). Для этого предварительно найдем остатки от деления степеней x n на примитивный полином p(x) = x 2 + x + 1: x 0 p(x) = 1 = 001; x 1 p(x) = x = 010 x 2 p(x) = x 2 = 011; x 3 p(x) = x + 1 = 001 Учитывая, что в десятичной записи 001 = 1, 010 = 2, 011 = 3 из этих остатков составим таблицу индексов для GF (2 2 ) n 0 1 2 3 2 n 1 2 3 1 ind n 3 0 1 2 162 Глава 3. Теория помехоустойчивого кодирования Теперь, пользуясь таблицей индексов несложно построить таблицу умножения для GF (2 2 ): + 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 × 1 2 3 1 1 2 3 2 2 3 1 3 3 1 2 Таблица сложения строится как побитовое сложение элементов по модулю 2. Совершенный код в GF (2 2 ) имеет параметры [n, k] = [5, 3]. Рассмотрим правила построения проверочных символов (e 1 e 2 ) по известным информационным (a 1 a 2 a 3 ): e 1 = 3 X k=1 a k , e 2 = 3 X k=1 ka k Передаваемая кодовая комбинация теперь имеет вид F = (a 1 a 2 a 3 e 1 e 2 ). Допустим в кодовой комбинации возникла одна ошибка: F = (a 1 a 2 a 3 e 1 e 2 ). Тогда значение ошибки E вычисляется по формуле E = e 1 + e 1 , где e 1 = 3 P k=1 a k , а позициция ошибки j j = e 2 + e 2 E , где e 2 = 3 P k=1 ke k . Если j = 0 или E = 0, то ошибка в проверочных символах. Пример 39. Закодировать сообщение a = (321). Решение. Пользуясь таблицами сложения и умножения поля GF (2 2 ) найдем проверочные символы e 1 = X a k = 3 + 2 + 1 = 0, e 2 = X ka k = 1 · 3 + 2 · 2 + 3 · 1 = 3 + 3 + 3 = 3. Т.о. кодовая комбинация принимает вид F = (32103). N Допустим во время передачи информации в сообщении появилась ошибка во 2-м символе F = (31103). Пример 40. Обнаружить и исправить ошибку в сообщении F = (31103). 3.8. Совершенные недвоичные коды 163 Решение. Из принятой кодовой комбинации имеем (e 1 = 0, e 2 = 3). Пользуясь таблицами сложения и умножения поля GF (2 2 ) найдем новые проверочные символы e 1 = X a k = 3 + 1 + 1 = 3, e 2 = X ka k = 1 · 3 + 2 · 1 + 3 · 1 = 3 + 2 + 3 = 2. Тогда значение ошибки E вычисляется по формуле E = e 1 + e 1 = 0 + 3 = 3, а позициция ошибки j j = e 2 + e 2 E = 3 + 2 E = 1 3 = 2. Прибавляя E = 3 ко второму символу a 2 + E = 1 + 3 = 2 получим информационную комбинацию a = (321). N Задача 3.23. Обнаружить и исправить единичную ошибку совершенного кода [n,k]=[5,3] в GF (2 2 ). N F N F N F N F 1 (2, 2, 1, 1, 3) 9 (3, 2, 2, 2, 0) 17 (2, 0, 2, 2, 0) 25 (3, 1, 2, 1, 3) 2 (1, 2, 2, 2, 0) 10 (2, 1, 0, 1, 1) 18 (3, 3, 3, 1, 3) 26 (1, 0, 3, 0, 2) 3 (0, 2, 2, 2, 0) 11 (3, 2, 3, 1, 3) 19 (2, 3, 1, 2, 2) 27 (0, 3, 0, 2, 2) 4 (2, 1, 1, 1, 1) 12 (3, 3, 1, 1, 3) 20 (1, 3, 1, 0, 2) 28 (1, 0, 2, 0, 2) 5 (3, 0, 3, 1, 3) 13 (3, 2, 0, 1, 3) 21 (1, 2, 1, 1, 3) 29 (3, 1, 0, 1, 3) 6 (1, 2, 1, 0, 2) 14 (3, 3, 1, 2, 2) 22 (3, 0, 1, 1, 3) 30 (2, 1, 2, 2, 0) 7 (1, 3, 1, 2, 2) 15 (2, 3, 2, 1, 0) 23 (3, 2, 3, 1, 3) 31 (0, 2, 1, 1, 3) 8 (2, 2, 3, 2, 0) 16 (2, 1, 3, 1, 1) 24 (3, 1, 1, 1, 3) 32 (3, 1, 1, 1, 3) 3.8.3 Совершенный код в GF (2 3 ) Совершенный код в GF (2 3 ) имеет параметры [n, k] = [9, 7]. Рассмотрим правила построения проверочных символов (e 1 e 2 ) по известным информационным (a 1 a 2 ...a 7 ): e 1 = 7 X k=1 a k , e 2 = 7 X k=1 ka k Передаваемая кодовая комбинация теперь имеет вид F = (a 1 a 2 a 3 a 4 a 5 a 6 a 7 e 1 e 2 ). Допустим в кодовой комбинации возникла одна ошибка: F = (a 1 a 2 a 3 a 4 a 5 a 6 a 7 e 1 e 2 ). Тогда значение ошибки E вычисляется по формуле E = e 1 + e 1 , 164 Глава 3. Теория помехоустойчивого кодирования где e 1 = 7 P k=1 a k , а позициция ошибки j j = e 2 + e 2 E , где e 2 = 7 P k=1 ke k . Если j = 0 или E = 0, то ошибка в проверочных символах. Пример 41. Закодировать сообщение a = (6543456). Решение. Пользуясь таблицами сложения и умножения поля GF (2 3 ) найдем проверочные символы e 1 = X a k = 6 + 5 + 4 + 3 + 4 + 5 + 6 = 3, e 2 = X ka k = 1 · 6 + 2 · 5 + 3 · 4 + 4 · 3 + 5 · 4 + 6 · 5 + 7 · 6 = 6 + 1 + 7 + 7 + 2 + 3 + 4 = 2 Т.о. кодовая комбинация принимает вид F = (654345632). N Допустим во время передачи информации в сообщении появилась ошибка во 3-м символе F = (651345632). Пример 42. Обнаружить и исправить ошибку в сообщении F = (651345632). Решение. Из принятой кодовой комбинации имеем (e 1 = 3, e 2 = 2). Пользуясь таблицами сложения и умножения поля GF (2 3 ) найдем новые проверочные символы e 1 = X a k = 6 + 5 + 1 + 3 + 4 + 5 + 6 = 6, e 2 = X ka k = 1 · 6 + 2 · 5 + 3 · 1 + 4 · 3 + 5 · 4 + 6 · 5 + 7 · 6 = 6 + 1 + 3 + 7 + 2 + 3 + 4 = 6 Тогда значение ошибки E вычисляется по формуле E = e 1 + e 1 = 3 + 6 = 5, а позициция ошибки j j = e 2 + e 2 E = 2 + 6 E = 4 5 = 4 · 2 = 3. Прибавляя E = 5 к третьему символу a 3 + E = 1 + 5 = 4 выделим информационную комбинацию a = (6543456). N Задача 3.24. Обнаружить и исправить единичную ошибку совершенного кода [n,k]=[9,7] над GF (2 3 ). 3.8. Совершенные недвоичные коды 165 N F N F N F 1 (4, 4, 4, 3, 5, 2, 6, 1, 6) 11 (2, 3, 2, 1, 6, 4, 0, 7, 6) 21 (1, 2, 3, 2, 7, 5, 1, 7, 2) 2 (2, 3, 5, 1, 2, 3, 6, 3, 3) 12 (4, 6, 4, 3, 5, 2, 6, 1, 6) 22 (6, 3, 2, 2, 7, 0, 7, 2, 7) 3 (1, 2, 0, 2, 1, 5, 1, 7, 2) 13 (2, 3, 4, 0, 2, 3, 6, 3, 3) 23 (4, 2, 4, 3, 5, 2, 6, 1, 6) 4 (2, 3, 2, 0, 2, 3, 6, 0, 0) 14 (4, 3, 5, 0, 6, 7, 3, 2, 0) 24 (2, 0, 4, 1, 2, 3, 6, 3, 3) 5 (2, 3, 2, 5, 1, 4, 0, 7, 6) 15 (1, 2, 3, 2, 6, 5, 1, 7, 2) 25 (2, 3, 2, 1, 1, 4, 4, 7, 6) 6 (2, 3, 4, 1, 2, 3, 3, 3, 3) 16 (4, 3, 2, 1, 1, 1, 3, 0, 5) 26 (4, 3, 2, 0, 1, 6, 3, 0, 5) 7 (2, 3, 2, 5, 1, 3, 6, 1, 6) 17 (2, 3, 2, 4, 2, 3, 0, 0, 0) 27 (0, 3, 5, 2, 6, 7, 3, 2, 0) 8 (6, 3, 2, 1, 1, 6, 3, 0, 5) 18 (2, 3, 4, 1, 2, 6, 6, 3, 3) 28 (2, 0, 2, 3, 1, 3, 6, 1, 6) 9 (4, 3, 5, 2, 0, 7, 3, 2, 0) 19 (2, 0, 5, 5, 1, 3, 6, 1, 6) 29 (2, 0, 2, 4, 2, 3, 6, 0, 0) 10 (1, 7, 2, 2, 7, 0, 7, 2, 7) 20 (1, 4, 2, 2, 7, 0, 7, 2, 7) 30 (2, 3, 4, 5, 2, 3, 6, 3, 3) 166 Глава 3. Теория помехоустойчивого кодирования 3.9 Коды Рида-Соломона Коды Рида-Соломона были предложены в 1960 Ирвином Ридом (Irving S. Reed) и Густавом Соломоном (Gustave Solomon), являвшимися сотрудниками Линкольнской лаборатории МТИ. Они использованы на алгоритме декодирования Berlekamp-Massey. Коды Рида-Соломона это блочные коды, которые применяются для исправления ошибок во многих системах: - устройствах памяти CD, DVD, штриховых кодах, - беспроводных или мобильных каналах (сотовые телефоны, микроволновые каналы и т.д.) - спутниковых коммуникацях - цифровом телевидении DVB (digital video broadcast). - скоростных модемах ADSL, xDSL. 3.9.1 Исправление 1 ошибки несовершенного кода [n, k] q = [7, 5] 8 Как правило пораждающий полином в конечном поле Галуа GF (2 3 ) имеет вид g(x) = b+2t−1 Y i=b (x ⊕ 2 i ), где t - количество ошибок, исправляемых кодом, b - произвольная целая константа (обычно 0 или 1). Пример 3.43. Порождающие полиномы для исправления t=1 ошибки: b=0: g(x) = 2t−1 Y i=0 (x ⊕ 2 i ) = (x ⊕ 2 0 )(x ⊕ 2 1 ) = x 2 + (1 + 2)x + (1 · 2) = x 2 + 3x + 2, b=1: g(x) = 2t Y i=1 (x ⊕ 2 i ) = (x ⊕ 2 1 )(x ⊕ 2 2 ) = x 2 + (2 + 4)x + (2 · 4) = x 2 + 6x + 3, b=2: g(x) = 2t+1 Y i=2 (x ⊕ 2 i ) = (x ⊕ 2 2 )(x ⊕ 2 3 ) = x 2 + (4 + 3)x + (4 · 3) = x 2 + 7x + 7. N Здесь мы непосредственно используем таблицы сложения и умножения для поля Галуа GF (2 3 ). Однако, данные полиномы приводимы по определению и поэтому не формируют совершенных кодов, хотя и удобны в использовании. Сведем для 3.9. Коды Рида-Соломона 167 удобства в таблицу коэффициенты (c i , d i ), необходимые для формирования проверочных символов по информационным для исправления 1 ошибки: e 1 = 4 X i=0 c i a i , e 2 = 4 X i=0 d i a i , b g(x) c i d i 0 x 2 + 3x + 2 (5, 2, 4, 7, 3) (4, 3, 5, 6, 2) 1 x 2 + 6x + 3 (6, 7, 7, 1, 6) (2, 2, 3, 1, 3) 2 x 2 + 7x + 7 (4, 4, 2, 4, 7) (1, 5, 1, 3, 7) 3 x 2 + 5x + 1 (1, 5, 6, 6, 5) (5, 6, 6, 5, 1) 4 x 2 + 1x + 4 (7, 3, 1, 5, 1) (7, 4, 2, 4, 4) 5 x 2 + 2x + 6 (3, 1, 3, 2, 2) (6, 1, 7, 7, 6) 6 x 2 + 4x + 5 (2, 6, 5, 3, 4) (3, 7, 4, 2, 5) Построение кода сводится к следующей последовательности действий. Представим информационную последовательность (a 0 , a 1 , a 2 , ..., a n ) в виде полинома u(x) = n X i=0 a i x n−i = a 0 x n + a 1 x n−1 + a 2 x n−2 + ... + a n−1 x + a n Сдвинем информационную последовательность на r = 2t разрядов влево, для этого умножим информационный полином u(x) на x r : m(x) = x r u(x). Разделим полученный полином на порождающий: m(x) g(x) = C(x) + R(x) g(x) , или m(x) = C(x) · g(x) + R(x). Запишем полином остатков в виде R(x) = r X i=0 e i x r−i Передаваемая кодовая комбинация теперь имеет вид F = a 0 a 1 a 2 a 3 a 4 e 1 e 2 или F (x) = a 0 x 6 + a 1 x 5 + a 2 x 4 + a 3 x 3 + a 4 x 2 + e 1 x + e 2 168 Глава 3. Теория помехоустойчивого кодирования Обозначим принятую кодовую комбинацию через F (x) = A 6 x 6 + A 5 x 5 + A 4 x 4 + A 3 x 3 + A 2 x 2 + A 1 x + A 0 или F = (A 6 A 5 A 4 A 3 A 2 A 1 A 0 ). Допустим, принятая кодовая комбинация F имеет 1 ошибку. Прямой алгебраический метод исправления 1 ошибки заключается в следующем. Находим синдромы ошибки по формулам S 0 = F (2 b ) = A 6 (2 b ) 6 + A 5 (2 b ) 5 + A 4 (2 b ) 4 + A 3 (2 b ) 3 + A 2 (2 b ) 1 + A 1 (2 b ) + A 0 , S 1 = F (2 b+1 ) = A 6 (2 b+1 ) 6 + A 5 (2 b+1 ) 5 + A 4 (2 b+1 ) 4 + A 3 (2 b+1 ) 3 + A 2 (2 b+1 ) 2 + A 1 (2 b+1 ) + A 0 Решая уравнение S 1 = S 0 σ по таблице индексов для GF (2 3 ) находим локатор ошибки λ = ind σ и значение ошибки S 0 = σ b E. Ошибка величиной E находится на λ месте кодовой последовательности. Очевидно, что размерность синдрома позволяет локализовать только 7 разрядов, поэтому прямой алгебраический метод применяется для кода [7,5], с пятью информационными символами. Пример 3.44. Пусть передается информационная последовательность (20105). Для построения кода Рида-Соломона с b=0, исправляющего одну ошибку сформируем по информационным символам (a 0 , a 1 , a 2 , a 3 , a 4 ) = (20105) проверочные (e 1 , e 2 ): e 1 = 5a 0 + 2a 1 + 4a 2 + 7a 3 + 3a 4 , e 2 = 4a 0 + 3a 1 + 5a 2 + 6a 3 + 2a 4 , или e 1 = 5 · 2 + 2 · 0 + 4 · 1 + 7 · 0 + 3 · 5 = 1 + 4 + 4 = 1, e 2 = 4 · 2 + 3 · 0 + 5 · 1 + 6 · 0 + 2 · 5 = 3 + 5 + 1 = 7. Код Рида-Соломона имеет вид F = (A 6 A 5 A 4 A 3 A 2 A 1 A 0 ) = (2010517). Допустим в передаваемой кодовой последовательности возникла ошибка в 3 разряде F = (2015517). Учитывая, что F (x) = 2 · x 6 + 0 · x 5 + 1 · x 4 + 5 · x 3 + 5 · x 2 + 1 · x 1 + 7 · 1, 3.9. Коды Рида-Соломона 169 определяем синдром ошибки с помощью выражений S 0 = F (2 b ), и S 1 = F (2 b+1 ). Поскольку у нас b=0, то S 0 = F (2 0 ) = F (1) = 2 · 1 6 + 0 · 1 5 + 1 · 1 4 + 5 · 1 3 + 5 · 1 2 + 1 · 1 + 7 = 2 + 1 + 5 + 5 + 1 + 7 = 5, S 1 = F (2 1 ) = F (2) = 2 · 2 6 + 0 · 2 5 + 1 · 2 4 + 5 · 2 3 + 5 · 2 2 + 1 · 2 + 7, = 2 · 5 + 0 · 7 + 1 · 6 + 5 · 3 + 5 · 4 + 1 · 2 + 7, = 1 + 6 + 4 + 2 + 2 + 7 = 4. Для определения локатора ошибки решаем уравнение S 1 = S 0 σ, 4 = 5σ ⇒ σ = 4 · 5 −1 Из таблицы умножения для GF (2 3 ) видим, что 5 · 2 = 1, т.е. обратным элементом для 5 является 2 (т.е. 5 −1 = 2): σ = 4 · 5 −1 = 4 · 2 = 3. По таблице индексов находим локатор ошибки λ = ind σ, λ = ind 3 = 3. Величину ошибки E найдем по формуле S 0 = σ b E, 5 = 1 · E. Т.е. к символу A 3 необходимо прибавить E = 5: F = (2015517) → F = (2010517) и передаваемую информационную последовательность записать в виде a = (20105) 7 N Пример 3.45. Пусть передается информационная последовательность (54321). Для построения кода Рида-Соломона с b=2, исправляющего одну ошибку сформируем по информационным символам (a 0 , a 1 , a 2 , a 3 , a 4 ) = (54321) проверочные (e 1 , e 2 ). Учитывая что для b=2 по таблице c = (44247), d = (15137) получим e 1 = (a · c) = (54321)(44247), e 2 = (a · d) = (54321)(15137) 7 Данный результат F = (2010517) можно проверить следующими способами. a) Если для a = (20105) мы получим e 1 = 1, e 2 = 7, то задача решена правильно. b) Если для F = (2010517) мы получим S 0 = 0, S 1 = 0, то задача решена правильно. 170 Глава 3. Теория помехоустойчивого кодирования или e 1 = 5 · 4 + 4 · 4 + 3 · 2 + 2 · 4 + 1 · 7 = 2 + 6 + 6 + 3 + 7 = 6, e 2 = 5 · 1 + 4 · 5 + 3 · 1 + 2 · 3 + 1 · 7 = 5 + 2 + 3 + 6 + 7 = 5. Код Рида-Соломона имеет вид F = (A 6 A 5 A 4 A 3 A 2 A 1 A 0 ) = (5432165). Допустим в передаваемой кодовой последовательности возникла ошибка в 5 разряде F = (5732165). Учитывая, что F (x) = 5 · x 6 + 7 · x 5 + 3 · x 4 + 2 · x 3 + 1 · x 2 + 6 · x 1 + 5 · 1, определяем синдром ошибки с помощью выражений S 0 = F (2 b ), и S 1 = F (2 b+1 ). Поскольку у нас b=2, то S 0 = F (2 2 ) = F (4) = 5 · 4 6 + 7 · 4 5 + 3 · 4 4 + 2 · 4 3 + 1 · 4 2 + 6 · 4 + 5 = 5 · 7 + 7 · 3 + 3 · 2 + 2 · 5 + 1 · 6 + 6 · 4 + 5 = 6 + 2 + 6 + 1 + 6 + 5 + 5 = 5, S 1 = F (2 3 ) = F (3) = 5 · 3 6 + 7 · 3 5 + 3 · 3 4 + 2 · 3 3 + 1 · 3 2 + 6 · 3 + 5 = 5 · 3 6 + 7 · 3 5 + 3 · 3 4 + 2 · 3 3 + 1 · 3 2 + 6 · 3 + 5 = 5 · 6 + 7 · 2 + 3 · 7 + 2 · 4 + 1 · 5 + 6 · 3 + 5 = 3 + 5 + 2 + 3 + 5 + 1 + 5 = 6. Для определения локатора ошибки решаем уравнение S 1 = S 0 σ, 6 = 5σ ⇒ σ = 7. По таблице индексов находим локатор ошибки λ = ind σ, λ = ind 7 = 5. Т.е. ошибка в символе A 5 . Величину ошибки E найдем по формуле S 0 = σ b E, 5 = 7 2 · E = 3 · E ⇒ E = 3. Т.е. к символу A 5 необходимо прибавить E = 3: F = (5732165) → F = (5432165) и передаваемую информационную последовательность записать в виде a = (54321). N 3.9. Коды Рида-Соломона 171 Задача 3.25. Обнаружить и исправить ошибку в информационной кодовой комбинации RSC[7,5] сформированной производящим полиномом g(x) поля GF (2 3 ). N g(x) F N g(x) F i 1 x 2 + 3x + 2 (2, 0, 1, 7, 5, 7, 4) 16 x 2 + 6x + 3 (7, 0, 1, 7, 5, 6, 3) 2 x 2 + 6x + 3 (5, 6, 1, 5, 5, 7, 2) 17 x 2 + 7x + 7 (5, 6, 3, 5, 7, 0, 5) 3 x 2 + 7x + 7 (6, 3, 3, 4, 2, 7, 4) 18 x 2 + 5x + 1 (6, 6, 1, 7, 5, 5, 2) 4 x 2 + 5x + 1 (4, 5, 1, 3, 1, 5, 3) 19 x 2 + 1x + 4 (7, 0, 4, 5, 2, 6, 1) 5 x 2 + 1x + 4 (5, 5, 4, 4, 2, 2, 2) 20 x 2 + 2x + 6 (4, 5, 1, 7, 3, 5, 7) 6 x 2 + 2x + 6 (6, 4, 1, 0, 7, 4, 7) 21 x 2 + 4x + 5 (1, 0, 0, 5, 2, 2, 1) 7 x 2 + 4x + 5 (7, 0, 0, 4, 2, 6, 2) 22 x 2 + 3x + 2 (4, 0, 3, 7, 5, 7, 0) 8 x 2 + 3x + 2 (2, 5, 1, 7, 4, 5, 2) 23 x 2 + 6x + 3 (6, 5, 1, 4, 5, 5, 3) 9 x 2 + 6x + 3 (0, 3, 1, 5, 4, 4, 1) 24 x 2 + 7x + 7 (6, 6, 2, 5, 6, 2, 0) 10 x 2 + 7x + 7 (4, 5, 6, 3, 4, 5, 6) 25 x 2 + 5x + 1 (7, 5, 3, 4, 5, 6, 5) 11 x 2 + 5x + 1 (5, 3, 1, 5, 5, 6, 4) 26 x 2 + 1x + 4 (0, 3, 1, 5, 6, 1, 2) 12 x 2 + 1x + 4 (6, 3, 5, 3, 5, 1, 7) 27 x 2 + 2x + 6 (1, 0, 3, 4, 3, 4, 6) 13 x 2 + 2x + 6 (7, 4, 1, 5, 2, 7, 4) 28 x 2 + 4x + 5 (2, 4, 4, 5, 5, 2, 5) 14 x 2 + 4x + 5 (1, 5, 1, 3, 5, 4, 2) 29 x 2 + 3x + 2 (2, 3, 1, 1, 3, 4, 4) 15 x 2 + 3x + 2 (3, 4, 2, 1, 5, 2, 1) 30 x 2 + 6x + 3 (5, 4, 3, 2, 1, 5, 0) 172 Глава 3. Теория помехоустойчивого кодирования 3.9.2 Исправление 2 ошибок несовершенного кода [n, k] q = [7, 3] 8 Для исправления t = 2 ошибок мы создаем r = 2t = 4 проверочных символа которые могут принимать 8 4 = 4096 значений, достаточных для обнаружения 1 и 2 ошибок максимум в n = 13 разрядах, поскольку: 1 + C 1 13 7 + C 2 13 7 2 = 3914 < 8 4 Расмотрим алгебраический метод декодирования для исправления 2 ошибок. Пример 3.46. Порождающие полиномы для исправления t=2 ошибок: b=0: g(x) = 2t−1 Y i=0 (x ⊕ 2 i ) = 3 Y i=0 (x ⊕ 2 i ) = (x ⊕ 2 0 )(x ⊕ 2 1 )(x ⊕ 2 2 )(x ⊕ 2 3 ) = (x ⊕ 1)(x ⊕ 2)(x ⊕ 4)(x ⊕ 3) = x 4 + (1 + 2 + 4 + 3)x 3 +(1 · 2 + 1 · 4 + 1 · 3 + 2 · 4 + 2 · 3 + 4 · 3)x 2 +(1 · 2 · 4 + 1 · 2 · 3 + 1 · 4 · 3 + 2 · 4 · 3)x + 1 · 2 · 4 · 3 = x 4 + 4x 3 + (2 + 4 + 3 + 3 + 6 + 7)x 2 + (3 + 6 + 7 + 5)x + 5 = x 4 + 4x 3 + 7x 2 + 7x + 5 b=1: g(x) = 2t Y i=1 (x ⊕ 2 i ) = 4 Y i=1 (x ⊕ 2 i ) = (x ⊕ 2 1 )(x ⊕ 2 2 )(x ⊕ 2 3 )(x ⊕ 2 4 ) = (x ⊕ 2)(x ⊕ 4)(x ⊕ 3)(x ⊕ 6) = x 4 + 3x 3 + 4x 2 + 2x + 3 b=2: g(x) = 2t+1 Y i=2 (x ⊕ 2 i ) = 5 Y i=2 (x ⊕ 2 i ) = (x ⊕ 2 2 )(x ⊕ 2 3 )(x ⊕ 2 4 )(x ⊕ 2 5 ) = (x ⊕ 4)(x ⊕ 3)(x ⊕ 6)(x ⊕ 7) = x 4 + 6x 3 + 4x 2 + 6x + 1 N Сведем для удобства в таблицу коэффициенты (c i , d i , h i , f i ), необходимые для формирования проверочных символов по информационным для исправления 2 ошибок: e 1 = X a k c k , e 2 = X a k d k , e 3 = X a k h k , e 4 = X a k f k b g(x) c i d i h i f i 0 x 4 + 4x 3 + 7x 2 + 7x + 5 (2, 1, 4) (3, 6, 7) (5, 4, 7) (5, 2, 5) 1 x 4 + 3x 3 + x 2 + 2x + 3 (6, 4, 3) (1, 1, 1) (6, 5, 2) (7, 5, 3) 2 x 4 + 6x 3 + 4x 2 + 6x + 1 (1, 6, 6) (6, 3, 4) (4, 3, 6) (6, 6, 1) 3 x 4 + 7x 3 + 6x 2 + x + 6 (3, 5, 7) (2, 5, 6) (1, 1, 1) (3, 4, 6) 4 x 4 + 5x 3 + 5x 2 + 3x + 2 (5, 2, 5) (7, 4, 5) (7, 6, 3) (4, 1, 2) 5 x 4 + x 3 + 2x 2 + 5x + 7 (4, 3, 1) (4, 7, 2) (3, 2, 5) (2, 7, 7) 6 x 4 + 2x 3 + 3x 2 + 4x + 4 (7, 7, 2) (5, 2, 3) (2, 7, 4) (1, 3, 4) 3.9. Коды Рида-Соломона 173 Для исправления 2 ошибок возьмем 4 проверочных разряда. Передаваемая кодовая комбинация теперь имеет вид F = a 0 a 1 a 2 e 1 e 2 e 3 e 4 или F (x) = a 0 x 6 + a 1 x 5 + a 2 x 4 + e 1 x 3 + e 2 x 2 + e 3 x + e 4 Допустим, принятая кодовая комбинация F (x) = A 6 x 6 + A 5 x 5 + A 4 x 4 + A 3 x 3 + A 2 x 2 + A 1 x + A 0 имеет 2 ошибки. Прямой алгебраический метод исправления 2 ошибок заключается в следующем. Находим синдромы ошибки по формулам S k = F (2 b+k ). Например, для b=0, получим S 0 = F (2 0 ) = F (1) = A 6 1 6 + A 5 1 5 + A 4 1 4 + A 3 1 3 + A 2 1 2 + A 1 1 1 + A 0 , S 1 = F (2 1 ) = F (2) = A 6 2 6 + A 5 2 5 + A 4 2 4 + A 3 2 3 + A 2 2 2 + A 1 2 1 + A 0 , S 2 = F (2 2 ) = F (4) = A 6 4 6 + A 5 4 5 + A 4 4 4 + A 3 4 3 + A 2 4 2 + A 1 4 1 + A 0 , S 3 = F (2 3 ) = F (3) = A 6 3 6 + A 5 3 5 + A 4 3 4 + A 3 3 3 + A 2 3 2 + A 1 3 1 + A 0 Решая уравнение S 2 S 3 = S 0 S 1 S 1 S 2 σ 2 σ 1 находим многочлен локаторов ошибок σ(x) = 1 + σ 1 x + σ 2 x 2 = ν Y k=1 (1 + α k x) корни которого равны обратным величинам локаторов ошибок. Для нахождения значения ошибок наобходимо решить систему S 0 S 1 = α b 1 α b 2 α b+1 1 α b+1 2 e 1 e 2 Ошибка величиной E k = ind(e k ) находится на λ k = ind(σ k ) месте кодовой последовательности. Очевидно, что размерность синдрома позволяет локализовать только 7 разрядов, поэтому прямой алгебраический метод применяется для кода [7,3], с тремя информационными символами. Пример 3.47. Пусть передается информационная последовательность (753). Для построения кода Рида-Соломона с b=0, исправляющего две ошибки сформируем по информационным символам (a 0 , a 1 , a 2 ) = (753) проверочные (e 1 , e 2 , e 3 , e 4 ): e 1 = X a k c k , e 2 = X a k d k , e 3 = X a k h k , e 4 = X a k f k 174 Глава 3. Теория помехоустойчивого кодирования или e 1 = 2a 1 + 1a 2 + 4a 3 = 2 · 7 + 1 · 5 + 4 · 3 = 5 + 5 + 7 = 7, e 2 = 3a 1 + 6a 2 + 7a 3 = 3 · 7 + 6 · 5 + 7 · 3 = 2 + 3 + 2 = 3, e 3 = 5a 1 + 4a 2 + 7a 3 = 5 · 7 + 4 · 5 + 7 · 3 = 6 + 2 + 2 = 6, e 4 = 5a 1 + 2a 2 + 5a 3 = 5 · 7 + 2 · 5 + 5 · 3 = 6 + 1 + 4 = 3. Код Рида-Соломона для данной информационной последовательности имеет вид F = (7537363). Допустим в передаваемой кодовой последовательности возникли ошибки в 4 и 5 разряде F = (7537363) ⇒ F = (7667363). Учитывая, что F (x) = 7 · x 6 + 6 · x 5 + 6 · x 4 + 7 · x 3 + 3 · x 2 + 6 · x 1 + 3 · 1, определяем синдром ошибки с помощью выражений S 0 = F (2 b ) = 7 · 1 6 + 6 · 1 5 + 6 · 1 4 + 7 · 1 3 + 3 · 1 2 + 6 · 1 + 3 = 6 S 1 = F (2 b+1 ) = 7 · 2 6 + 6 · 2 5 + 6 · 2 4 + 7 · 2 3 + 3 · 2 2 + 6 · 2 + 3 = 1, S 2 = F (2 b+2 ) = 7 · 4 6 + 6 · 4 5 + 6 · 4 4 + 7 · 4 3 + 3 · 4 2 + 6 · 4 + 3 = 4, S 3 = F (2 b+3 ) = 7 · 3 6 + 6 · 3 5 + 6 · 3 4 + 7 · 3 3 + 3 · 3 2 + 6 · 3 + 3 = 0. Для определения локатора ошибки нам необходимо решить систему S 2 S 3 = S 0 S 1 S 1 S 2 σ 2 σ 1 или 4 0 = 6 1 1 4 σ 2 σ 1 Методом Крамера, получим ∆ = 6 1 1 4 = 6 · 4 − 1 · 1 = 5 + 1 = 4 ∆ 2 = 4 1 0 4 = 4 · 4 − 0 · 1 = 6 + 0 = 6 ∆ 1 = 6 4 1 0 = 6 · 0 − 1 · 4 = 0 + 4 = 4 Из таблицы умножения для GF (2 3 ) видим, что 4 · 7 = 1, т.е. обратным элементом для 4 является 7. Тогда σ 2 = ∆ 2 ∆ = 6 4 = 6 · 7 = 4, σ 1 = ∆ 1 ∆ = 4 4 = 4 · 7 = 1. 3.9. Коды Рида-Соломона 175 Построим многочлен локаторов ошибки σ(x) = 1 + σ 1 x + σ 2 x 2 = 1 + x + 4x 2 Для решения данного уравнения воспользуемся формулами Виета x 1 + x 2 = σ 1 x 1 · x 2 = σ 2 или x 1 + x 2 = 1 x 1 · x 2 = 4 По таблицам сложения и умножения для GF (2 3 ) находим x 1 = 6, x 2 = 7, тогда σ(x) = 1 + x + 4x 2 = (1 + 6x)(1 + 7x) = (1 + 2 4 x)(1 + 2 5 x). и ошибки локализованы в разрядах λ 1 = ind x 1 = ind 6 = 4 и λ 2 = ind x 2 = ind 7 = 5. Т.е. ошибки в символах A 4 и A 5 (коэффициенты при степенях x 4 и x 5 ) полинома F (x). Для нахождения значения ошибок решим систему S 0 S 1 = x b 1 x b 2 x b+1 1 x b+1 2 e 1 e 2 или 6 1 = 1 1 6 7 e 1 e 2 Методом Крамера, получим ∆ = 1 1 6 7 = 1 · 7 − 6 · 1 = 7 + 6 = 1 ∆ 1 = 6 1 1 7 = 6 · 7 − 1 · 1 = 4 + 1 = 5 ∆ 2 = 1 6 6 1 = 1 · 1 − 6 · 6 = 1 + 2 = 3 Тогда e 1 = ∆ 1 ∆ = 5 1 = 5, e 2 = ∆ 2 ∆ = 3 1 = 3. Т.о. мы имеем ошибку в разряде x 4 со значением E 4 = 5 и в разряде x 5 со значением E 5 = 3. Исправляя ошибки, получим F (x) = 7 · x 6 + 6 · x 5 + 6 · x 4 + 7 · x 3 + 3 · x 2 + 6 · x 1 + 3 · 1, F (x) = 7 · x 6 + (6 + 3) · x 5 + (6 + 5) · x 4 + 7 · x 3 + 3 · x 2 + 6 · x 1 + 3 · 1 = 7 · x 6 + 5 · x 5 + 3 · x 4 + 7 · x 3 + 3 · x 2 + 6 · x 1 + 3 · 1 176 Глава 3. Теория помехоустойчивого кодирования или F (x) = (7 667363) ⇒ F (x) = (7 537363) и исправленная информационная последовательность имеет вид a = (753) 8 . N Пример 3.48. Построить код Рида-Соломона, иправляющего 2 ошибки для информационной последовательности a = (264). Для построения кода Рида-Соломона с b=3, исправляющего две ошибки сформируем по информационным символам (a 0 , a 1 , a 2 ) = (264) проверочные (e 1 , e 2 , e 3 , e 4 ): e 1 = X a k c k , e 2 = X a k d k , e 3 = X a k h k , e 4 = X a k f k Из таблицы коэффициентов для кода [7, 3] 8 для b=3, g(x) = x 4 + 7x 3 + 6x 2 + x + 6 имеем: c = (357), d = (256), h = (111), f = (346) или e 1 = (a · c) = 2 · 3 + 6 · 5 + 4 · 7 = 6 + 3 + 1 = 4, e 2 = (a · d) = 2 · 2 + 6 · 5 + 4 · 6 = 4 + 3 + 5 = 2, e 3 = (a · h) = 2 · 1 + 6 · 1 + 4 · 1 = 2 + 6 + 4 = 0, e 4 = (a · f) = 2 · 3 + 6 · 4 + 4 · 6 = 6 + 5 + 5 = 6. Код Рида-Соломона для данной информационной последовательности имеет вид F = (2644206). Допустим в передаваемой кодовой последовательности возникли ошибки в 2 и 6 разряде F = (2644206) ⇒ F = (7644606). Учитывая, что F (x) = 7 · x 6 + 6 · x 5 + 4 · x 4 + 4 · x 3 + 6 · x 2 + 0 · x 1 + 6 · 1, определяем синдром ошибки при b=3 с помощью выражений S 0 = F (2 b ) = F (2 3 ) = F (3) = 7 · 3 6 + 6 · 3 5 + 4 · 3 4 + 4 · 3 3 + 6 · 3 2 + 0 · 3 + 6 = 7 · 6 + 6 · 2 + 4 · 7 + 4 · 4 + 6 · 5 + 0 · 3 + 6 = 4 + 7 + 1 + 6 + 3 + 0 + 6 = 1 S 1 = F (2 b+1 ) = F (2 4 ) = F (6) = 7 · 6 6 + 6 · 6 5 + 4 · 6 4 + 4 · 6 3 + 6 · 6 2 + 0 · 6 + 6 = 1 = 7 · 3 + 6 · 5 + 4 · 4 + 4 · 7 + 6 · 2 + 0 · 6 + 6 = 2 + 3 + 6 + 1 + 7 + 0 + 6 = 7, 8 Данный результат F = (7537363) можно проверить следующими способами. a) Если для a = (753) мы получим e = (7363), то задача решена правильно. b) Если для F = (7537363) мы получим S 0 = S 1 = S 2 = S 3 = 0, то задача решена правильно. 3.9. Коды Рида-Соломона 177 S 2 = F (2 b+2 ) = F (2 5 ) = F (7) = 7 · 7 6 + 6 · 7 5 + 4 · 7 4 + 4 · 7 3 + 6 · 7 2 + 0 · 7 + 6 = 7 · 4 + 6 · 6 + 4 · 5 + 4 · 2 + 6 · 3 + 0 · 7 + 6 = 1 + 2 + 2 + 3 + 1 + 0 + 6 = 5, S 3 = F (2 b+3 ) = F (2 6 ) = F (5) = 7 · 5 6 + 6 · 5 5 + 4 · 5 4 + 4 · 5 3 + 6 · 5 2 + 0 · 5 + 6 = 7 · 2 + 6 · 4 + 4 · 3 + 4 · 6 + 6 · 7 + 0 · 5 + 6 = 5 + 5 + 7 + 5 + 4 + 0 + 6 = 0. Для определения локатора ошибки нам необходимо решить систему S 2 S 3 = S 0 S 1 S 1 S 2 σ 2 σ 1 или 5 0 = 1 7 7 5 σ 2 σ 1 Методом Крамера, получим ∆ = 1 7 7 5 = 1 · 5 − 7 · 7 = 5 + 3 = 6 ∆ 2 = 5 7 0 5 = 5 · 5 − 0 · 7 = 7 + 0 = 7 ∆ 1 = 1 5 7 0 = 1 · 0 − 7 · 5 = 0 + 6 = 6 Из таблицы умножения для GF (2 3 ) видим, что 6 · 3 = 1, т.е. обратным элементом для 6 является 3. Тогда σ 2 = ∆ 2 ∆ = 7 6 = 7 · 3 = 2, σ 1 = ∆ 1 ∆ = 6 6 = 6 · 3 = 1. Построим многочлен локаторов ошибки σ(x) = 1 + σ 1 x + σ 2 x 2 = 1 + x + 2x 2 Для решения данного уравнения воспользуемся формулами Виета x 1 + x 2 = σ 1 x 1 · x 2 = σ 2 или x 1 + x 2 = 1 x 1 · x 2 = 2 По таблицам сложения и умножения для GF (2 3 ) находим x 1 = 4, x 2 = 5, тогда σ(x) = 1 + x + 2x 2 = (1 + 4x)(1 + 5x) = (1 + 2 2 x)(1 + 2 6 x). 178 Глава 3. Теория помехоустойчивого кодирования и ошибки локализованы в разрядах λ 1 = ind x 1 = ind 4 = 2 и λ 2 = ind x 2 = ind 5 = 6. Т.е. ошибки в символах A 2 и A 6 (коэффициенты при степенях x 2 и x 6 ) полинома F (x). Для нахождения значения ошибок решим систему S 0 S 1 = x b 1 x b 2 x b+1 1 x b+1 2 e 1 e 2 или 1 7 = 4 3 5 3 4 4 5 4 e 1 e 2 = 5 6 2 3 e 1 e 2 Методом Крамера, получим ∆ = 5 6 2 3 = 5 · 3 − 2 · 6 = 4 + 7 = 3 ∆ 1 = 1 6 7 3 = 1 · 3 − 7 · 6 = 3 + 4 = 7 ∆ 2 = 5 1 2 7 = 5 · 7 − 2 · 1 = 6 + 2 = 4 Тогда e 1 = ∆ 1 ∆ = 7 3 = 7 · 6 = 4, e 2 = ∆ 2 ∆ = 4 3 = 4 · 6 = 5. Т.о. мы имеем ошибку в разряде x 2 со значением E 2 = 4 и в разряде x 6 со значением E 6 = 5. Исправляя ошибки, получим F = (7644606) ⇒ F = (2644206) и исправленная информационная последовательность имеет вид a = (264) 9 . N Пример 3.49. Обнаружить и исправить ошибки в принятой последовательности F = (6254420) кода [n, k] = [7, 3] построеной при помощи полинома b=4 в GF (2 3 ). Учитывая, что F (x) = 6 · x 6 + 2 · x 5 + 5 · x 4 + 4 · x 3 + 4 · x 2 + 2 · x 1 + 0 · 1, определяем синдром ошибки при b=4 с помощью выражений S 0 = F (2 b ) = F (2 4 ) = F (6) = 6 · 6 6 + 2 · 6 5 + 5 · 6 4 + 4 · 6 3 + 4 · 6 2 + 2 · 6 + 0 = 6 · 3 + 2 · 5 + 5 · 4 + 4 · 7 + 4 · 2 + 2 · 6 + 0 = 1 + 1 + 2 + 1 + 3 + 7 + 0 = 7 9 Данный результат F = (2644206) можно проверить следующими способами. a) Если для a = (264) мы получим e = (4206), то задача решена правильно. b) Если для F = (2644206) мы получим S 0 = S 1 = S 2 = S 3 = 0, то задача решена правильно. 3.9. Коды Рида-Соломона 179 S 1 = F (2 b+1 ) = F (2 5 ) = F (7) = 6 · 7 6 + 2 · 7 5 + 5 · 7 4 + 4 · 7 3 + 4 · 7 2 + 2 · 7 + 0 = 6 · 4 + 2 · 6 + 5 · 5 + 4 · 2 + 4 · 3 + 2 · 7 + 0 = 5 + 7 + 7 + 3 + 7 + 5 + 0 = 4, S 2 = F (2 b+2 ) = F (2 6 ) = F (5) = 6 · 5 6 + 2 · 5 5 + 5 · 5 4 + 4 · 5 3 + 4 · 5 2 + 2 · 5 + 0 = 6 · 2 + 2 · 4 + 5 · 3 + 4 · 6 + 4 · 7 + 2 · 5 + 0 = 7 + 3 + 4 + 5 + 1 + 1 + 0 = 5, S 3 = F (2 b+3 ) = F (2 7 ) = F (1) = 6 · 1 6 + 2 · 1 5 + 5 · 1 4 + 4 · 1 3 + 4 · 1 2 + 2 · 1 + 0 = 6 · 1 + 2 · 1 + 5 · 1 + 4 · 1 + 4 · 1 + 2 · 1 + 0 = 6 + 2 + 5 + 4 + 4 + 2 + 0 = 3. Для определения локатора ошибки нам необходимо решить систему S 2 S 3 = S 0 S 1 S 1 S 2 σ 2 σ 1 , или 5 3 = 7 4 4 5 σ 2 σ 1 Методом Крамера, получим ∆ = 7 4 4 5 = 7 · 5 − 4 · 4 = 6 + 6 = 0 ∆ 2 = 5 4 3 5 = 5 · 5 − 3 · 4 = 7 + 7 = 0 ∆ 1 = 7 5 4 3 = 7 · 3 − 4 · 5 = 2 + 2 = 0 Поскольку главный определитель равен нулю, мы заключаем, что в принятой последовательности произошла только одна ошибка. Для ее локализации решаем уравнение S 1 = σS 0 или 4 = σ7 ⇒ σ = 6 = 2 4 Т.е. ошибка локализована в символе A 4 (коэффициент при степени x 4 полинома F (x)). Значение ошибки находим по формуле S 0 = σ b E или 7 = 6 4 E = 4E ⇒ E = 4 −1 7 = 7 · 7 = 3. Т.о. мы имеем ошибку в разряде x 4 со значением E 4 = 3. Исправляя ошибку, получим F = (6254420) ⇒ F = (6264420) 180 Глава 3. Теория помехоустойчивого кодирования и исправленная информационная последовательность имеет вид a = (626) 10 . N Задача 3.26. Обнаружить и исправить 2 ошибки в информационной кодовой комбинации RSC[7,3] сформированной производящим полиномом g(x) поля GF (2 3 ). N g(x) F i N g(x) F i 1 x 4 + 4x 3 + 7x 2 + 7x + 5 (4562373) 16 x 4 + 3x 3 + 1x 2 + 2x + 3 (1615153) 2 x 4 + 3x 3 + 1x 2 + 2x + 3 (2732576) 17 x 4 + 6x 3 + 4x 2 + 6x + 1 (7563113) 3 x 4 + 6x 3 + 4x 2 + 6x + 1 (1247370) 18 x 4 + 7x 3 + 6x 2 + 1x + 6 (4431737) 4 x 4 + 7x 3 + 6x 2 + 1x + 6 (5116230) 19 x 4 + 5x 3 + 5x 2 + 3x + 2 (4661674) 5 x 4 + 5x 3 + 5x 2 + 3x + 2 (2325111) 20 x 4 + 1x 3 + 2x 2 + 5x + 7 (5564312) 6 x 4 + 1x 3 + 2x 2 + 5x + 7 (3333005) 21 x 4 + 2x 3 + 3x 2 + 4x + 4 (5471253) 7 x 4 + 2x 3 + 3x 2 + 4x + 4 (4117765) 22 x 4 + 4x 3 + 7x 2 + 7x + 5 (2715001) 8 x 4 + 4x 3 + 7x 2 + 7x + 5 (2453626) 23 x 4 + 3x 3 + 1x 2 + 2x + 3 (6262477) 9 x 4 + 3x 3 + 1x 2 + 2x + 3 (0650027) 24 x 4 + 6x 3 + 4x 2 + 6x + 1 (5525355) 10 x 4 + 6x 3 + 4x 2 + 6x + 1 (0114252) 25 x 4 + 7x 3 + 6x 2 + 1x + 6 (3270440) 11 x 4 + 7x 3 + 6x 2 + 1x + 6 (2421121) 26 x 4 + 5x 3 + 5x 2 + 3x + 2 (2264425) 12 x 4 + 5x 3 + 5x 2 + 3x + 2 (3634162) 27 x 4 + 1x 3 + 2x 2 + 5x + 7 (5253561) 13 x 4 + 1x 3 + 2x 2 + 5x + 7 (3615206) 28 x 4 + 2x 3 + 3x 2 + 4x + 4 (2727517) 14 x 4 + 2x 3 + 3x 2 + 4x + 4 (2264027) 29 x 4 + 4x 3 + 7x 2 + 7x + 5 (1426013) 15 x 4 + 4x 3 + 7x 2 + 7x + 5 (3262616) 30 x 4 + 3x 3 + 1x 2 + 2x + 3 (2535555) 10 Данный результат F = (6264420) можно проверить следующими способами. a) Если для a = (626) мы получим e = (4420), то задача решена правильно. b) Если для F = (6264420) мы получим S 0 = S 1 = S 2 = S 3 = 0, то задача решена правильно. |