Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
b = 1. Теорема 47. Двоичный код БЧХ длины n = 2 m −1 с порождающим многочленом g(x) = НОК{M (1) (x), M (2) (x), . . . , M (2t−1) (x)} имеет параметры [n = 2 m − 1, k ≥ n − tm, d ≥ 2t + 1]. Доказательство. При p = 2 в силу свойства 7 минимальных многочленов (см. разд. 7.6.) имеем M (2i) (x) = M (i) (x). Отсюда следует, что степень g(x) может быть понижена. А именно, определяя g(x), можно не рассматривать минимальные многочлены для степеней примитивного эле- мента с четными показателями. Конструктивное расстояние δ данного в теореме кода БЧХ равно 2t. В силу отме- ченного свойства минимальных многочленов, коды с конструктивными расстояниями 2t и 2t + 1 совпадают, для каждого из них порождающий многочлен имеет вид g(x) = НОК{M (1) (x), M (3) (x), . . . , M (2t−1) (x)}. Таким образом, deg g(x) ≤ tm. Для размерности кода выполняется соответственно k ≥ n − tm. Проверочная матрица кода равна H = 1 α α 2 . . . α n−1 1 α 3 α 6 . . . α (n−1)3 . . . 1 α 2t−1 α 2(2t−1) . . . α (n−1)(2t−1) , где каждый элемент должен быть заменен соответствующим двоичным вектором- столбцом длины m. Второй столбец содержит степени элемента α: α, α 3 , . . . , α 2t−1 , показатели которых лежат в различных циклотомических классах по модулю 2 m − 1. N В разд. 8.2. показано, что двоичный код Хэмминга имеет циклическое представ- ление. Этот факт также непосредственно следует из доказанной теоремы. Следствие 10. Код БЧХ, исправляющий одну ошибку, имеет параметры [n = 2 m − 1, k = n − m, d = 3], порождающий многочлен g(x) = M (1) (x) и является кодом Хэмминга. 88 Глава 8. Коды БЧХ Следствие 11. Код БЧХ, исправляющий две ошибки, имеет параметры [n = 2 m − 1, k = n − 2m, d ≥ 5], где m ≥ 3 нечетно и порождающий многочлен g(x) = M (1) (x) · M (3) (x). Доказательство. Кодовое расстояние непосредственно следует из теоремы 47. Докажем, что g(x) = M (1) (x) · M (3) (x) и k = n − 2m. По теореме 47 имеем g(x) = НОК{M (1) (x), M (2) (x), M (3) (x), M (4) (x)} = НОК{M (1) (x), M (3) (x)}. Далее нам потребуются некоторые свойства минимальных многочленов из разд. 7.6. Поскольку α — примитивный элемент поля GF (2 m ), то по свойству 6 минимальных многочленов степень M (1) (x) равна m. Так как m нечетно, имеем (3, 2 m − 1) = 1. По лемме 7 из разд. 6.2. получаем, что порядок элемента α 3 равен 2 m − 1. Таким образом, многочлен M (3) (x) примитивен и по свойству 6 его степень также равна m. Минимальные многочлены M (1) (x) и M (3) (x) неприводимы согласно свойству 1 минимальных многочленов, поэтому g(x) = M (1) (x) · M (3) (x), и размерность кода k в точности равна n − 2m. N Коды БЧХ (более точно: примитивные коды БЧХ) асимптотически плохие, а именно справедливо следующее утверждение. Теорема 48 Для любой бесконечной последовательности [n, k, d]-кодов БЧХ над GF (q) скорость кода k/n и отношение d/n стремятся к нулю с ростом n. 8.7. Коды Рида-Соломона 8.7.1. Определение и свойства Коды Рида-Соломона — это коды БЧХ над GF (q), q = p m , длина n которых равна q − 1, q 6= 2, а порождающий многочлен имеет вид g(x) = (x − α b ) · (x − α b+1 ) · . . . · (x − α b+δ−2 ) (8.3) для некоторых b ≥ 0, δ > 1. Иногда удобно рассматривать b равным единице. Такие коды представляют собой значительный практический и теоретический интерес и обладают целым рядом хороших свойств. В следующей теореме, например, покажем, что для кода Рида-Соломона можно точно вычислить как кодовое расстояние, так и мощность. Теорема 49. Код Рида-Соломона длины n имеет мощность q n−δ+1 и кодовое расстояние d = n − k + 1 = δ. 8.7. Коды Рида-Соломона 89 Доказательство. Поскольку порождающий многочлен кода Рида-Соломона дли- ны q − 1 имеет вид (8.3) для некоторых b ≥ 0, δ > 1, код Рида-Соломона — это БЧХ-код с конструктивным расстоянием δ длины n = q −1, q 6= 2. Размерность этого циклического кода равна k = n − deg g(x) = n − δ + 1. Согласно границе Синглтона (см. теорему 4 разд. 1.2.), если B — (n, k, d)-код, то n − k ≥ d − 1. Иными словами, d ≤ n − k + 1. Отсюда для кода Рида-Соломона имеем d = n − k + 1, а следовательно, этот код является MDS-кодом. N Достоинства кодов Рида-Соломона: 1. Коды Рида-Соломона удобно использовать, когда требуется код, длина которо- го меньше, чем размер поля, так как, являясь MDS-кодами, они имеют наибольшее возможное минимальное расстояние. 2. Они используются для получения двоичных кодов с очень большими мини- мальными расстояниями. 3. Коды Рида-Соломона используются при построении каскадных кодов с хоро- шими параметрами. 4. Они используются при построении кодов, исправляющих пакеты ошибок (см. подробнее разд. 8.7.2.). Пример 8. Рассмотрим код Рида-Соломона над GF (5) длины 4 с конструктив- ным расстоянием 3. В качестве примитивного элемента поля GF (5) возьмем, на- пример, α = 2, тогда g(x) = (x − α)(x − α 2 ) = (x − 2)(x − 4) = x 2 + 4x + 3. Код Рида-Соломона имеет 5 2 = 25 кодовых слов длины 4, среди них например, (3410), (2140), (0341), (3201) . . . . Упражнение 43. Найти все 25 кодовых слов этого кода. Добавление к коду общей проверки на четность не всегда увеличивает его мини- мальное расстояние, если коды недвоичные и есть слова нечетного веса. Например, добавление общей проверки на четность к коду над GF (3) с кодовой матрицей µ 1 1 1 0 0 0 0 1 1 1 ¶ не увеличивает кодовое расстояние. Однако для кодов Рида-Соломона с порождаю- щим многочленом g(x) = (x − α) · (x − α 2 ) · . . . · (x − α δ−1 ) кодовое расстояние всегда увеличивается на 1. Теорема 50. Пусть P — [n = p m − 1, k, d]-код Рида-Соломона с порождающим многочленом g(x) = (x − α) · (x − α 2 ) · . . . · (x − α δ−1 ). Тогда расширение каждого кодового слова c = (c 0 , c 1 , . . . , c n−1 ) посредством добавле- ния общей проверки на четность над GF (p) c n = − n−1 X i=0 c i приводит к коду с параметрами [n + 1, k, d + 1]. 90 Глава 8. Коды БЧХ Доказательство. Пусть w(c) = d. Кодовому слову c соответствует многочлен c(x), и минимальный вес c увеличивается до d + 1, если n−1 X i=0 c i = −c n 6= 0. Но c(x) = c 0 + c 1 x + . . . + c n−1 x n−1 и, следовательно, c(1) = n−1 X i=0 c i = −c n . Покажем, что c(1) 6= 0. По теореме 38 (см. разд. 7.2.) имеем c(x) = a(x)g(x), где g(x) — порождающий многочлен кода. По определению g(x), поскольку α 0 не является его корнем заключаем, что g(1) 6= 0. Для a(x) имеем a(1) 6= 0, так как в противном случае многочлен c(x) делился бы на многочлен (x − 1) и, согласно границе БЧХ (см. теорему 45), кодовое слово c имело бы вес не менее чем d + 1. Следовательно, c(1) = a(1)g(1) 6= 0, то есть кодовое расстояние полученного кода увеличивается на 1. N Упражнение 44. Построить код Рида-Соломона с параметрами [3, 2, 2] над по- лем Галуа GF (4) = {0, 1, α, α 2 }, где α 2 + α + 1 = 0 и рассмотреть расширенный код с параметрами [4, 2, 3]. 8.7.2. Использование кодов Рида-Соломона для получения двоичных кодов Элементы поля GF (p m ) могут быть представлены m-векторами над GF (p) (вспомним пример поля GF (2 4 ), где элементы поля были представлены двоичными векторами длины 4). Рассмотрим q-значный код Рида-Соломона с параметрами [n = q − 1, k = n − δ + 1, d = δ] q , где q = p m . Произведя замену на p-значные векторы, получим p-значный код с па- раметрами [n 0 = nm, k 0 = km, d 0 ≥ d]. Если q = 2 m , то полученные двоичные коды имеют часто большое минимальное расстояние. Далее покажем это. Пусть v 1 , . . . , v m — базис векторного пространства GF (2 m ) над GF (2), т. е. базис в m-мерном единичном кубе E m . Тогда любой элемент β, принадлежащий GF (2 m ), представим в виде β = m X i=1 b i v i = b 1 v 1 + . . . + b m v m , где b i принадлежит GF (2). Рассмотрим отображение β → (b 1 , . . . , b m ). Это отобра- жение переводит линейные коды над GF (2 m ) в линейные над GF (2), т. е. сохраняет линейность, но необязательно при этом сохраняет цикличность! 8.8. Коды Юстесена 91 Построим из кода Рида-Соломона двоичный код с большим кодовым расстояни- ем. Пусть вектор c = (c 0 , . . . , c n−1 ) принадлежит [n, k, d]-коду Рида-Соломона над GF (2 m ). Заменим элементы c i соответствующими двоичными m-векторами и к каж- дому такому m-вектору добавим общую проверку на четность. Получим двоичный код с параметрами [n 0 = (m + 1)(2 m − 1), k 0 = mk, d 0 ≥ 2d = 2(2 m − k)]. Аналогичное преобразование можно применить к расширенному коду Рида-Соломона, что приводит к двоичному коду с параметрами [(m + 1)2 m , mk, d 0 ≥ 2(2 m − k + 1)]. Полученный код является каскадным кодом. Каскадные коды имеют широкое применение на практике, например, использу- ются при записи информации на компакт дисках. Повреждения в компакт дисках могут вызвать длинные последовательности ошибок. Ошибки в цифровой записи и воспроизведении бывают двух типов: 1) случайные (в несколько бит, обычно разбросаны по диску, их можно легко ис- править); 2) ошибки типа "потеря пакета". Определение. Пакетом длины s называется вектор, все ненулевые элементы которого расположены среди s подряд идущих компонент, из которых первая и по- следняя являются ненулевыми. Иначе говоря, ошибка составляет большое число последовательно расположенных бит. Например, в компакт дисках такая ошибка может быть вызвана физическим по- вреждением диска или крупным дефектом ленты. Эффект, вызванный таким дефек- том, может быть существенно уменьшен, если биты, составляющие посылку, распо- лагать не последовательно, а дискретно через некоторые интервалы (кадры). Тогда потерю сравнительно большого пакета ошибок можно рассматривать как случайную. Такой метод передачи данных использует код Рида-Соломона, а точнее двоичный код, полученный из кода Рида-Соломона. Иногда рассматриваются более сложные преобразования кода Рида-Соломона в двоичный с помощью процедуры перемеже- ния, с применением двух кодеров, например, при использовании функции четности для любого двоичного набора длины m либо каскадирования. Однако двоичный код, полученный из кода Рида-Соломона, все же довольно плохо исправляет случайные ошибки. В этом случае может быть использован код Юстесена. 8.8. Коды Юстесена Рассмотрим код Рида-Соломона над полем GF (2 m ) с параметрами [n = 2 m − 1, k, d = n − k + 1] 2 m . 92 Глава 8. Коды БЧХ Пусть α — примитивный элемент поля GF (2 m ). Рассмотрим произвольный вектор (a 0 , a 1 , a 2 , . . . , a n−1 ) кода Рида-Соломона и составим с помощью него вектор длины 2n над GF (2 m ) сле- дующего вида a = (a 0 , a 0 , a 1 , αa 1 , a 2 , α 2 a 2 , . . . , a n−1 , α n−1 a n−1 ). Заменяя в этом векторе каждый элемент a i из GF (2 m ) отвечающим ему двоичным вектором длины m, получаем двоичный вектор длины 2mn. Полученное множество двоичных слов образует код Юстесена с параметрами [N = 2mn, K = mk, D], который по построению является линейным кодом. Кодовое расстояние D определя- ется из следующего предложения. Утверждение 15. Минимальное расстояние D кода Юстесена удовлетворяет неравенству D ≥ w X i=1 i · µ 2m i ¶ , где для кодового расстояния d исходного кода Рида-Соломона справедливо: w X i=1 µ 2m i ¶ ≤ d ≤ w+1 X i=1 µ 2m i ¶ . Доказательство. Любое ненулевое кодовое слово кода Юстесена содержит по крайней мере d различных двоичных векторов длины 2m, где u 6= 0 и v 6= 0. Очевид- но, что количество различных векторов длины 2m малого веса невелико. Следова- тельно, вес любого ненулевого кодового слова кода Юстесена должен быть большим. Минимальный вес ненулевого слова кода Юстесена не меньше суммы весов d нену- левых двоичных векторов длины 2m минимально возможного веса, а именно: D ≥ w X i=1 i · µ 2m i ¶ + (w + 1) Ã d − w X i=1 µ 2m i ¶! , где в первом слагаемом под знаком суммы стоит количество единиц в наборе длины 2m, а во втором — количество оставшихся столбцов в двоичном аналоге проверочной матрицы. Причем вес w определяется из соотношения w X i=1 µ 2m i ¶ ≤ d ≤ w+1 X i=1 µ 2m i ¶ . N Нетрудно видеть, что коды Юстесена являются каскадными кодами. Они также хороши тем, что являются асимптотически хорошими кодами. Глава 9 Другие коды 9.1. Матрицы Адамара, коды Адамара 9.1.1. Матрицы Адамара Определение. Матрицей Адамара порядка n называется n × n матрица H, элементами которой являются +1 и −1 такая, что H · H T = nE n , где E n — единичная матрица размера n × n. Это равенство эквивалентно тому, что любые две строки матрицы ортогональны, т. е. их скалярное произведение в поле действительных чисел равно 0, а скалярное произведение любой строки на саму себя равно n. Матрица H носит название матрицы Адамара, поскольку ее детерминант дости- гает границы, принадлежащей Адамару. Справедлива Теорема 51 (Адамар Ж., 1897). Если A = (a ij ) — произвольная веществен- ная (n × n) матрица с элементами −1 ≤ a ij ≤ 1, то | det A| ≤ n n/2 (т. е. det 2 A ≤ n n ). Для матрицы Адамара справедливо det |