Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
f (x), задан- ную на положительной полуоси. Для произвольных положительных чисел β i , 30 Глава 3. Теорема Шеннона i = 1, . . . , k таких, что P k i=1 β i = 1 и любых x 1 , . . . , x k из участка выпуклости функ- ции f (x) выполняется неравенство Йенсена k X i=1 β i f (x i ) ≤ f à k X i=1 β i x i ! , причем равенство имеет место тогда и только тогда, когда x 1 = . . . = x k . Утверждение 9. Для источника A, определенного выше, справедливо H(A) ≤ log k. Доказательство. Рассмотрим функцию f (x) = log x. Она выпукла вверх при x > 0, поскольку ее вторая производная меньше нуля. Положим β i = p i . Тогда с учетом P k i=1 p i = 1 и неравенства Йенсена имеем H(A) = − k X i=1 p i log p i = k X i=1 p i log µ 1 p i ¶ ≤ log à k X i=1 p i 1 p i ! = log k. N Утверждение 10. Для произвольных q 1 , . . . , q k таких, что q i ≥ 0 и P k i=1 q i = 1 справедливо − k X i=1 p i log q i ≥ − k X i=1 p i log p i , причем равенство достигается только при q i = p i (таким образом значение энтро- пии минимизирует функцию f (q 1 , . . . , q k ) = − P k i=1 p i log q i ). Доказательство. Рассмотрим доказательство этого свойства в случае, когда все p i положительны (при p i = 0 для некоторого i = 1, . . . , k, доказательство аналогично с некоторыми модификациями). Воспользуемся неравенством Йенсена при β i = p i , x i = q i /p i , i = 1, . . . , k для функции f (x) = log x: k X i=1 p i log q i p i ≤ log à k X i=1 p i · q i p i ! = log à k X i=1 q i ! = log 1 = 0. Отсюда имеем k X i=1 p i log q i − k X i=1 p i log p i ≤ 0, откуда вытекает требуемое. Неравенство Йенсена переходит в равенство только то- гда, когда x 1 = . . . = x k или в нашем случае при q 1 /p 1 = . . . = q k /p k , т. е. когда векторы (q 1 , . . . , q k ) и (p 1 , . . . , p k ) пропорциональны и, следовательно, в силу k X i=1 q i = k X i=1 p i = 1 имеем q i = p i N 3.2. Свойства энтропии 31 Утверждение 11. Для любых случайных опытов A и B справедливо H(AB) ≤ H(A) + H(B), причем равенство достигается только когда опыты A и B независимы. Для бер- нуллиевских источников справедливо H(A N ) = N · H(A) для любого натурального N. Здесь AB обозначает произведение источников A и B : пусть A = µ a 1 a 2 . . . a k p 1 p 2 . . . p k ¶ , B = µ b 1 b 2 . . . b k q 1 q 2 . . . q k ¶ , тогда AB = µ (a i , b j ) p i q j ¶ , где i, j ∈ {1, 2, . . . , k}; A N — произведение N копий источника A. В дальнейшем нас будет интересовать случай событий с двумя исходами, по- скольку основная модель изучаемого нами канала связи — двоичный симметричный канал. В этой ситуации имеем функцию H(x) одного аргумента. В силу утверждения 8, она равна нулю при x = 0 и x = 1, согласно утверждения 9, достигает максимума, равного единице, в точке x = 1/2. Кроме того, для нее выполняется соотношение H(x) = H(1 − x), следовательно, функция H(x) симметрична относительно прямой x = 1/2, см. ее график на рис. 4. ½ x 0 H (x) 1 Рис. 4. График функции H(x) 32 Глава 3. Теорема Шеннона 3.3. Необходимые комбинаторно-вероятностные утверждения I. Неравенство Чебышева. При передачe информации по двоичному симмет- ричному каналу связи число ошибок в полученном слове является бернуллиевской случайной величиной τ , принимающей значения 0, 1, . . . , n, математическое ожида- ние E(τ ) которой равно np, а дисперсия D(τ ) равна np(1 − p). Если в кодовом слове x = (x 1 , . . . , x n ) произошло t ошибок, то, в силу того что имеем биномиальное рас- пределение, вероятность получить вектор ошибок e веса t равна P (e = v, w(v) = t) = p t (1 − p) n−t , т. е. зависит только от n и t. Теорема 12. Неравенство Чебышева. Если ξ — случайная величина с мате- матическим ожиданием E(ξ) и дисперсией D(ξ), тогда для любого ε > 0 справедливо P {|ξ − E(ξ)| ≥ ε} ≤ D(ξ) ε 2 . Выберем произвольное ε > 0. Для случайной величины τ обозначим через b сле- дующую величину: b = µ D(τ ) ε/2 ¶ 1/2 . Тогда, используя неравенство Чебышева, получаем P {|τ − E(τ )| ≥ b} ≤ D(τ ) b 2 = ε 2 . Откуда следует P {τ > ρ} ≤ ε 2 , (3.2) где ρ = [E(τ ) + b] = " np + µ np(1 − p) ε/2 ¶ 1/2 # . Неравенство (3.2) означает: вероятность того, что в результате произошедших в ка- нале τ ошибок полученное на приемном конце слово y находится от переданного кодового слова x на расстояние большее, чем ρ, мала (не превышает ε/2). Зафиксируем ε > 0, тогда для достаточно больших n величина ρ не превосходит (n/2), поскольку p < 1/2. II. Объем шара радиуса [pn]. Рассмотрим шар радиуса [pn] с центром в неко- торой вершине x ∈ E n : B [pn] (x) = {y | d(x, y) ≤ [pn]}. Оценим его объем |B [pn] (x)| = [pn] X i=0 C i n с помощью функции энтропии H(p). 3.4. Доказательство теоремы Шеннона 33 Лемма 2 Пусть 0 ≤ p ≤ 1 2 . Тогда справедлива оценка [pn] X i=0 C i n ≤ 2 nH(p) . Доказательство. Имеем 1 = (p + (1 − p)) n ≥ [pn] X i=0 C i n p i (1 − p) n−i ≥ [pn] X i=0 C i n p pn (1 − p) n−np = = [pn] X i=0 C i n 2 log(1−p) n ( p 1−p ) pn = [pn] X i=0 C i n 2 n log(1−p)+pn log( p 1−p ) = = [pn] X i=0 C i n 2 n(p log p+(1−p) log(1−p)) = 2 −nH(p) [pn] X i=0 C i n . Отсюда [pn] P i=0 C i n ≤ 2 nH(p) N III. Объем шара радиуса ρ = [E(τ ) + b]. Оценим объем шара радиуса ρ = [E(τ ) + b] с центром в некоторой вершине, используя функцию энтропии H(p). Лемма 3 Пусть 0 ≤ p ≤ 1 2 и ρ = [E(τ ) + b], где b = ³ D(τ ) ε/2 ´ 1/2 . Тогда 1 n log |B ρ (x)| ≤ H(p) − O ³ 1 √ n ´ при n → ∞. Доказательство. По лемме 2 имеем 1 n log |B ρ (x)| ≤ H ³ ρ n ´ = − ρ n log ρ n − ³ 1 − ρ n ´ log ³ 1 − ρ n ´ = = − [np + b] n log [np + b] n − ³ 1 − [np + b] n ´ log ³ 1 − [np + b] n ´ = = −p log p − (1 − p) log(1 − p) − O ³ b n ´ = H(p) − O ³ 1 √ n ´ при n → ∞, что доказывает лемму. N 3.4. Доказательство теоремы Шеннона Введем функцию f (y, x). Пусть x, y ∈ E n , тогда f (y, x) = ½ 0, если d(y, x) > ρ, 1, если d(y, x) ≤ ρ. 34 Глава 3. Теорема Шеннона Функция f (y, x) — характеристическая функция принадлежности вектора y шару с центром в вершине x, т. е. f (y, x) = ½ 0, если y 6∈ B ρ (x), 1, если y ∈ B ρ (x). Доказательство теоремы Шеннона. Выберем сколь угодно малую величину ε > 0. Рассмотрим случайный двоичный код длины n мощности M, т. е. выберем случайным образом кодовые слова x 1 , . . . , x M . Декодируем полученный вектор y сле- дующим образом: если существует в точности одно кодовое слово x i такое, что d(x i , y) ≤ ρ, то y декодируем в x i , в противном случае регистрируем ошибку или, если должны произвести декодирование в любом случае, всегда декодируем в x 1 Пусть P i , как и выше, вероятность того, что на выходе декодера получено слово, отличное от переданного слова x i . Для P i имеем следующую оценку сверху: P i ≤ X y∈E n P (y|x i ) £ 1 − f (y, x i ) + X j6=i f (y, x j ) ¤ = = X y∈E n P (y|x i )(1 − f (y, x i )) + X y∈E n X j6=i P (y|x i )f (y, x j ), (3.3) здесь выражение £ 1 − f (y, x i ) + P j6=i f (y, x j ) ¤ равно нулю тогда и только тогда, когда найдется единственное кодовое слово x i такое, что d(x i , y) ≤ ρ, в противном случае £ 1 − f (y, x i ) + X j6=i f (y, x j ) ¤ ≥ 1. Первая сумма в неравенстве (3.3) равна вероятности того, что полученное на приемном конце слово находится на расстоянии большем ρ от переданного кодового слова x. Согласно неравенству (3.2), оно не превышает ε/2. Таким образом, P C ≤ ε 2 + 1 M M X i=1 X y∈E n X j6=i P (y|x i )f (y, x j ). Основная идея дальнейшего доказательства состоит в том, что величина P ∗ (M, n, p) := min C∈e L {P C } меньше, чем ожидаемое значение, т. е. меньше математического ожидания P C над ансамблем e L всех возможных кодов C длины n, мощности M, взятых случайно. Отсюда имеем P ∗ (M, n, p) ≤ ε 2 + 1 M M X i=1 X y∈E n M X j=1,j6=i E(f (y, x j ))E(P (y|x i )) = 3.4. Доказательство теоремы Шеннона 35 = ε 2 + 1 M M X i=1 X y∈E n M X j=1,j6=i |B ρ | 2 n E(P (y|x i )) = = ε 2 + |B ρ | M · 2 n M X i=1 X y∈E n M X j=1,j6=i E(P (y|x j )) = = ε 2 + |B ρ | M · 2 n M X i=1 M X j=1,j6=i E à X y∈E n P (y|x j ) ! = = ε 2 + |B ρ | · M · (M − 1) M · 2 n ≤ ε 2 + M |B ρ | 2 n . Таким образом, P ∗ (M, n, p) − ε 2 ≤ M · 1 2 n · |B ρ |. Логарифмируя обе части, применяя лемму 3 и деля на n, получаем 1 n log(P ∗ (M, n, p) − ε 2 ) ≤ 1 n log M − (1 − H(p)) − O ³ 1 √ n ´ . Подставляя M = M n = 2 [R·n] в правую часть (вспомним, что по условию число R сколь угодно близко к пропускной способности C(p) = 1 − H(p)), получаем 1 n log(P ∗ (M, n, p) − ε 2 ) < −β < 0, где β — константа, равная C(p) − R. Отсюда P ∗ (M, n, p) < ε 2 + 2 −βn . Начиная с некоторого n будет выполняться 2 −βn < ε 2 , и, следовательно, P ∗ (M, n, p) < ε. Таким образом, P ∗ (M n , n, p) → 0 при n → ∞. Теорема доказана. Глава 4 Свитчинговые методы 4.1. Коды Васильева В 1959 г. Г. С. Шапиро и Д. С. Злотник предположили, что не существует совер- шенных кодов, не эквивалентных коду Хэмминга. В 1962 г. Ю. Л. Васильев опроверг эту гипотезу, предложив богатый класс неэквивалентных совершенных двоичных ко- дов. Рассмотрим этот итеративный способ построения для кодов с произвольными кодовыми расстояниями. Беря в качестве исходных кодов коды со специфически- ми параметрами, можно получить такие хорошие коды, как совершенные или коды Рида-Маллера. Рассмотрим произвольные двоичные коды B и C длины n с кодовыми расстоя- ниями d 1 и d 2 соответственно, где d 1 нечетно. Пусть λ — произвольная функция из кода C в множество {0, 1}, |x| = x 1 + . . . + x n (mod 2), где x = (x 1 , . . . , x n ). Теорема 13 Множество C 2n+1 = {(x + y, |x| + λ(y), x) | x ∈ B, y ∈ C} (4.1) является двоичным кодом длины 2n + 1, мощности |B| · |C| с кодовым расстоянием d ≥min{2d 1 + 1, d 2 }. Доказательство. Проверим параметры построенного кода, а именно его длину, мощность кода и кодовое расстояние. 1. Легко видеть, что 2n + 1 является длиной кода. 2. Поскольку x и y независимо пробегают множества B и C соответственно, мощ- ность кода C 2n+1 , очевидно, равна |C 2n+1 | = |B| · |C|. 3. Проверим, что кодовое расстояние равно d ≥ min{2d 1 + 1, d 2 }. Рассмотрим два произвольных различных кодовых слова: u = (x + y, |x| + λ(y), x), v = (x 0 + y 0 , |x 0 | + λ(y 0 ), x 0 ). 36 4.1. Коды Васильева 37 Возможны случаи. 3a. Если y = y 0 и x 6= x 0 , то, с учетом того что d(x, x 0 ) ≥ d 1 и d 1 нечетно, получаем d(u, v) = d((x, |x|, x), (x 0 , |x 0 |, x 0 )) ≥ 2d 1 + 1. 3b. Пусть y 6= y 0 и x = x 0 . Векторы y, y 0 принадлежат коду C n , следовательно, d(y, y 0 ) ≥ d 2 и получаем d(u, v) ≥ d(y, y 0 ) ≥ d 2 . 3c. Если y 6= y 0 и x 6= x 0 , то аналогично доказательству кодового расстояния в теореме Плоткина (см. теорему 9), используя предложение 4, получаем d(u, v) ≥ d(x, x 0 ) + d(x + y, x 0 + y 0 ) = = w(x − x 0 ) + w(x + y − x 0 − y 0 ) = = w(x − x 0 ) + w((y − y 0 ) + (x − x 0 )) ≥ ≥ w(x − x 0 ) + w(y − y 0 ) − w(x − x 0 ) = w(y − y 0 ) ≥ d 2 . Теорема доказана. N Рассмотрим применение этой конструкции для построения совершенных двоич- ных кодов. Теорема 14 (Васильев Ю. Л., 1962). Пусть C (n−1)/2 — произвольный со- вершенный код длины (n − 1)/2 = 2 m − 1, m ≥ 2 и λ — произвольная функция из кода C (n−1)/2 в множество {0, 1}. Множество V n = {(x + y, |x| + λ(y), x) : x ∈ E (n−1)/2 , y ∈ C (n−1)/2 } (4.2) является совершенным двоичным кодом длины n с кодовым расстоянием 3. Доказательство этой теоремы аналогично доказательству предыдущей. Код (4.2) будем далее называть кодом Васильева. Приведем несколько важных следствий, вы- текающих из этой теоремы. Следствие 2. При λ ≡ 0 конструкция Васильева, примененная к коду Хэммин- га H (n−1)/2 длины (n − 1)/2, дает код Хэмминга длины n: H n = { (x + y, |x|, x) : x ∈ E (n−1)/2 , y ∈ H (n−1)/2 }. Следствие 3. Если λ(y) + λ(y 0 ) 6= λ(y + y 0 ) для некоторых y, y 0 ∈ C (n−1)/2 , то код Васильева длины n является нелинейным. Поскольку функция λ произвольна, то, принимая во внимание предыдущие ите- ративные шаги, т. е. подставляя в формулу (4.2) снова произвольный код Васильева длины (n−1)/2, затем произвольный код Васильева длины (n−3)/4 и т. д., получаем следующее утверждение. 38 Глава 4. Свитчинговые методы Следствие 4. Число D n различных кодов Васильева длины n удовлетворяет следующей нижней оценке: D n ≥ 2 2 n+1 2 −log(n+1) · 2 2 n+5 4 −log(n+1) · 2 2 n+17 8 −log(n+1) . . . для достаточно больших n. Зная нижнюю оценку числа различных кодов длины n, легко вычислить нижнюю оценку числа неэквивалентных кодов с теми же параметрами. Для этого достаточно разделить число различных кодов на число различных автоморфизмов E n , равное 2 n · n!, здесь 2 n — число различных сдвигов на векторы из E n и n! — число различ- ных подстановок на n координатах. Нетрудно из следствия 4 получить следующее утверждение. Следствие 5. Для числа N n неэквивалентных кодов Васильева длины n спра- ведливо N n ≥ 2 2 n+1 2 −log(n+1) · 2 2 n+5 4 −log(n+1) при достаточно больших n. Эта оценка до 1996 г. оставалась лучшей нижней оценкой числа неэквивалентных совершенных кодов, несмотря на многочисленные усилия многих исследователей. Для n = 7 существует единственный совершенный код длины 7, для n = 15 су- ществует 11 неэквивалентных кодов Васильева длины 15 и, по крайней мере, 963 неэквивалентных кода, полученных каскадной конструкцией (см. [13]; о каскад- ных конструкциях см. следующую главу). Следует отметить, что классификация совершенных кодов даже длины 15 до сих пор не найдена. Обзоры результатов по совершенным кодам могут быть найдены в работах [13, 19]. Упражнение 18. Доказать следствие 4. Упражнение 19. Доказать следствие 5, используя формулу Стирлинга n n e −n √ 2nπ ≤ n! ≤ n n e 1−n √ 2nπ. (4.3) 4.2. Конструкция Моллара Рассмотрим конструкцию Моллара для двоичных кодов. Пусть P t и C m — про- извольные двоичные коды длин t и m соответственно с кодовыми расстояниями не менее 3, содержащие нулевые векторы. Пусть x = (x 11 , x 12 , . . . , x 1m , x 21 , . . . , x 2m , . . . , x t1 , . . . , x tm ) ∈ E tm . В этом разделе будем использовать следующую матричную запись для вектора x: i-я строка матрицы X равна x i1 x i2 . . . x im , где i = 1, . . . , t. Функции p 1 (x) и p 2 (x), определенные следующим образом: p 1 (x) = (σ 1 , σ 2 , . . . , σ t ) ∈ E t , p 2 (x) = (σ 0 1 , σ 0 2 , . . . , σ 0 m ) ∈ E m , где σ i = P m j=1 x ij и σ 0 j = P t i=1 x ij , называются обобщенными проверками на чет- ность. Пусть f — произвольная функция из P t в E m . 4.2. Конструкция Моллара 39 Теорема 15 (Моллар М., 1986). Множество C n = { (x, y + p 1 (x), z + p 2 (x) + f (y)) | x ∈ E tm , y ∈ P t , z ∈ C m } является двоичным кодом длины n = tm + t + m, с кодовым расстоянием 3. Доказательство. Легко проверить, что код C n имеет длину n = tm + t + m и мощность |C n | = |E tm | · |P t | · |C m |. Пусть u = (x, y + p 1 (x), z + p 2 (x) + f (y)), u 0 = (x 0 , y 0 + p 1 (x 0 ), z 0 + p 2 (x 0 ) + f (y 0 )) — два произвольных вектора из кода C n . Покажем, что d(u, u 0 ) ≥ 3. Возможны приведенные ниже случаи. 1. При x = x 0 имеем p 1 (x) = p 1 (x 0 ), p 2 (x) = p 2 (x 0 ) и, следовательно, при y 6= y 0 имеем d(u, u 0 ) ≥ d(y, y 0 ) ≥ 3. Аналогично при z 6= z 0 , y = y 0 . В случае y = y 0 , z = z 0 убеждаемся, что нулевой вектор принадлежит коду C n 2. Если d(x, x 0 ) = 1, то d(p 1 (x), p 1 (x 0 )) = d(p 2 (x), p 2 (x 0 )) = 1. Пусть y 6= y 0 , тогда d(y + p 1 (x), y 0 + p 1 (x 0 )) ≥ 2 и имеем d(u, u 0 ) ≥ 3. Пусть y = y 0 , тогда d(z + p 2 (x) + f (y), z 0 + p 2 (x 0 ) + f (y 0 )) ≥ 2 и снова имеем d(u, u 0 ) ≥ 3. 3. В случае d(x, x 0 ) = 2 расстояния d(p 1 (x), p 1 (x 0 )) и d(p 2 (x), p 2 (x 0 )) равны 0 или 2, но одновременно оба не могут быть равны нулю. Отсюда получаем, что равенства y + p 1 (x) = y 0 + p 1 (x 0 ), z + p 2 (x) + f (y) = z 0 + p 2 (x 0 ) + f (y 0 ) не выполняются одновременно и, следовательно, d(u, u 0 ) ≥ 3. N Замечания 1. В случае, когда P t и C m — произвольные совершенные двоичные коды длин t = 2 r − 1 и m = 2 s − 1 соответственно, код C n является совершенным двоичным кодом. 2. При m = 1, t = 2 r − 1 конструкция Моллара совпадает с конструкцией Васи- льева. 3. Существуют совершенные коды Моллара, неэквивалентные совершенным ко- дам Васильева. 40 Глава 4. Свитчинговые методы 4.3. Общая идея метода свитчинга Основная идея метода свитчинга состоит в следующем: в произвольном двоичном коде C длины n рассмотрим некоторое подмножество M кодовых слов. Если найдется в E n подмножество M 0 , отличное от множества M, и множество C 0 = (C \ M) ∪ M 0 является двоичным кодом с параметрами, совпадающими с параметрами кода C, то будем говорить, что код C 0 получен из кода C свитчингом множества M на множество M 0 . Результирующий код отличен или неэквивалентен исходному. Удобно рассмотреть общую идею метода свитчинга на примере совершенных ко- дов. Пусть дано подмножество M в пространстве E n . Множество M 0 получено из множества M инвертированием i-й координаты, i ∈ N = {1, 2, . . . , n}, всех слов M. Обозначим его M 0 = M + i. Множество M называется i-компонентой кода C, если K(M) = K(M + i), где K(M) — окрестность порядка 1 множества M. Легко видеть, что код C 0 = (C \ M) ∪ (M + i) также является совершенным кодом. Будем говорить, что код C 0 получен из кода C свитчингом i-компоненты M, (рис. 5). E n M+e i M C i Рис. 5. Свитчинг i-компоненты Рассмотрим основную идею более общего свитчингового подхода построения ко- дов (также на примере совершенных кодов), называемого методом α-компонент. Пусть α ⊆ N. Множество M назовем α-компонентой кода C, если для всех i ∈ α множество M является, в свою очередь, i-компонентой C. Сначала для каждой α-компоненты выбираем свое направление i из множества направлений α и заменя- ем (делаем "свитчинг") произвольное число i-компонент в каждой α-компоненте на новые i-компоненты такой же мощности. Затем производим замену полученных но- вых α-компонент на другие α-компоненты, делая свитчинги по неиспользованным из множества α направлениям. В итоге результирующий код остается по-прежнему со- вершенным, но отличным или даже неэквивалентным исходному. Метод α-компонент оказался особенно подходящим в применении его к коду Хэмминга, поскольку позво- ляет, разрушая групповую структуру кода Хэмминга, тем не менее следить за струк- турой нелинейного совершенного кода, получаемого вследствие серии свитчингов. Впервые свитчинговый способ построения кодов был предложен Ю. Л. Васи- льевым. Можно показать, что конструкция Моллара также является свитчинговой конструкцией. В 1996 г. С. В. Августиновичем и Ф. И. Соловьевой был предложен способ построения совершенных двоичных кодов посредством метода α-компонент (примененного к коду Хэмминга), который после 30-летнего перерыва дал первое су- щественное улучшение нижней оценки числа неэквивалентных совершенных кодов. 4.4. Некоторые свойства совершенных кодов 41 С помощью этого подхода была решена серия проблем, касающихся структуры со- вершенных кодов: например, обнаружены совершенные коды с тривиальной группой автоморфизмов, доказано существование несистематических совершенных кодов, ко- дов полного ранга. Ф. И. Соловьевой доказано существование совершенных двоич- ных кодов с i-компонентами различной мощности и структуры. Метод α-компонент получил дальнейшее развитие в работах С. А. Малюгина, Д. С. Кротова, С. В. Ав- густиновича (см. подробнее [13]). 4.4. Некоторые свойства совершенных кодов 4.4.1. Дистанционная инвариантность Код называется дистанционно инвариантным, если число A i (n) всех кодовых слов на расстоянии i от фиксированного кодового слова не зависит от выбора этого кодового слова. В 1957 г. С. П. Ллойд и независимо в 1959 г. Г. С. Шапиро и Д. С. Злотник до- казали, что произвольный совершенный код является дистанционно инвариантным. В этом и следующем параграфах приведем с доказательствами несколько красивых теорем о свойствах совершенных кодов с кодовым расстоянием 3, принадлежащих Г. С. Шапиро и Д. С. Злотнику. Теорема 16 (Шапиро Г. С., Злотник Д. С., 1959). Пусть C — произ- вольный совершенный код с кодовым расстоянием 3. Число кодовых слов на рассто- янии k от данного кодового слова x ∈ C не зависит от выбора этого кодового слова и от выбора кода и зависит только от расстояния k. Доказательство. Обозначим число кодовых слов на расстоянии k от кодового слова x через A k . Без ограничения общности рассмотрим код, содержащий вектор x = 0 n , где n — длина кода C. Построим систему линейных уравнений для A k , k = 0, . . . , n. Все числа A k однозначно будут вычислены из этой системы. Рассмотрим k-й слой E n k (все векторы веса k) в кубе E n . Согласно свойству плот- ной упакованности кода C, все векторы из E n k разобьются на следующие три под- множества: 1) кодовые слова веса k. Их число в точности равно A k ; 2) векторы, которые принадлежат сферам, окружающим все кодовые слова из E n k−1 , имеется (n − k + 1) · A k−1 таких векторов; 3) векторы, принадлежащие сферам с центрами в кодовых словах из E n k+1 , имеется (k + 1) · A k+1 таких векторов. Отсюда получаем следующую систему из n + 1 линейных уравнений с n + 1 неиз- вестными: A 0 = 1, A 1 = A 2 = 0, µ n k ¶ = (k + 1)A k+1 + A k + (n − k + 1)A k−1 , k = 2, 3, . . . , n, здесь числа A k с отрицательными индексами полагаются равными нулю (см. рис. 6). 42 Глава 4. Свитчинговые методы E n k+1 k–1 k k+1 n–k+1 A k+1 A k A k 1 – Рис. 6. Иллюстрация к теореме 16 Используя производящую функцию A 0 + A 1 t + . . . A n t n , можно найти точный вид A k , k = 0, 1, . . . , n, а именно: A 2k = 1 n + 1 µµ n 2k ¶ + (−1) k n µ (n − 1)/2 k ¶¶ , A 2k+1 = 1 n + 1 µµ n 2k + 1 ¶ + (−1) k+1 n µ (n − 1)/2 k ¶¶ и тем самым убедиться, что система имеет единственное решение. N Складывая последние два равенства, получаем A 2k + A 2k+1 = µ n 2k ¶ + µ n 2k + 1 ¶ n + 1 , что дает возможность сделать представленный ниже вывод. Следствие 6. Произвольный совершенный код длины n, содержащий нулевой вектор, имеет равномерное распределение по парам соседних слоев E n 2k и E n 2k+1 , k = 0, . . . , (n − 1)/2 куба E n . Из этой теоремы вытекают также следующие полезные свойства. Следствие 7. Для каждого кодового слова x ∈ C, где C — произвольный со- вершенный код длины n, антиподальный ему вектор x + 1 n также принадлежит коду C. Это свойство антиподальности оказалось чрезвычайно важным для исследования многих нетривиальных свойств совершенных двоичных кодов. Следствие 8. Число кодовых слов веса (n − 1)/2 произвольного совершенного кода длины n, содержащего нулевой вектор, равно A (n−1)/2 = 1 n + 1 µµ n (n − 1)/2 ¶ + n µ (n − 1)/2 (n − 3)/4 ¶¶ . 4.4. Некоторые свойства совершенных кодов 43 4.4.2. О существовании совершенных кодов Здесь рассмотрим несколько теорем о существовании совершенных кодов. Дока- зательство следующей очень важной теоремы весьма нетривиально и может быть найдено в работе [1]. Теорема 17. О существовании совершенных кодов (Зиновьев В. А., Ле- онтьев В. К., Тиетвайнен А., 1972). Нетривиальный совершенный код над лю- бым полем Галуа GF (q) должен иметь те же самые параметры, что и один из кодов Хэмминга или Голея, т. е.: 1) q-значный (n = (q m − 1)/(q − 1), n − m, 3)-код; 2) двоичный [23, 12, 7]-код Голея; 3) троичный [11, 6, 5] 3 -код Голея. Оба кода Голея единственны с точностью до эквивалентности и существует мно- го неэквивалентных совершенных q-значных кодов, q ≥ 2 (см. также следствие 5). Под тривиальным совершенным кодом понимается код, состоящий либо из одного кодового слова, либо из двух антиподальных (в случае, если n нечетно). В 1949 г. М. Ж. И. Голей построил двоичный совершенный [23, 12, 7]-код. Теорема 18 (Шапиро Г. С., Злотник Д. С., 1959). Единственными совер- шенными двоичными кодами с расстоянием 7 является код с параметрами кода Голея длины 23 и тривиальный код длины 7. Доказательство. Если существует совершенный двоичный код длины n, раз- мерности k, с кодовым расстоянием 7, то 2 n : µ 1 + µ n 1 ¶ + µ n 2 ¶ + µ n 3 ¶¶ = 2 k и, следовательно, 1 + µ n 1 ¶ + µ n 2 ¶ + µ n 3 ¶ = 2 r , где r = n − k. Умножая на 6 и преобразовывая левую часть последнего равенства, получаем (n 2 − n + 6)(n + 1) = 3· 2 r+1 . Следовательно, первый или второй сомножители в левой части этого равенства де- лятся на 3. Имеется два случая. 1. Пусть 3|(n 2 − n + 6). Тогда n + 1 = 2 l , n 2 − n + 6 = 3· 2 r−l+1 и, значит, выполняется (2 l − 1) 2 − (2 l − 1) + 6 = 3· 2 r−l+1 и 2 2l − 3· 2 l + 8 = 3· 2 r−l+1 . (4.4) 44 Глава 4. Свитчинговые методы При l = 3 имеем тривиальный код длины n = 7. Пусть l > 3 и n > 7. Из равенства (4.4) имеем 2 3 (2 2l−3 − 3· 2 l−3 + 1) = 3· 2 r−l+1 . Здесь первый сомножитель в левой части сравним с нулем по модулю 2, второй — с единицей по тому же модулю. Анализируя сомножители правой части, приходим к заключению, что 2 3 = 2 r−l+1 и, следовательно, r − l + 1 = 3. Отсюда n 2 − n + 6 = 3· 2 3 , что противоречит n > 7 (n должно быть целым числом). 2. Пусть 3|(n + 1). В этом случае имеем n + 1 = 3· 2 l , n 2 − n + 6 = 2 r−l+1 , откуда (3· 2 l − 1) 2 − (3· 2 l − 1) + 6 = 2 r−l+1 и 9· 2 2l − 9· 2 l + 8 = 2 r−l+1 , 2 3 (9· 2 2l−3 − 9· 2 l−3 + 1) = 2 r−l+1 , 9· 2 2l−3 − 9· 2 l−3 + 1 = 2 r−l−2 , 9· 2 2l−3 − 9· 2 l−3 = 2 r−l−2 − 1. Для равенства должно выполняться 2 l−3 = 1. Отсюда l = 3 и n + 1 = 3· 2 3 = 24. Ины- ми словами, получаем возможность для существования кода длины 23, с кодовым расстоянием 7, что завершает доказательство теоремы. N В следующей теореме показано неконструктивным методом, что количество со- вершенных двоичных кодов с расстоянием более 4 конечно. Доказательство теоремы является следствием одного глубокого результата Зигеля из теории чисел. Лемма 4 (Зигель). Пусть f (x) — многочлен, принимающий целые значения при целых значениях переменной x. Если f (x) не является степенью линейного многочлена, умноженного на константу, то наибольший простой делитель числа f (n) неограниченно возрастает при n → ∞. Теорема 19 (Шапиро Г. С., Злотник Д. С., 1959). Количество совершенных двоичных кодов длины n, с кодовым расстоянием d ≥ 5 конечно. Доказательство. Чтобы доказать теорему, мы должны убедиться, что много- член f (x), определенный как f (x) = 1 + µ x 1 ¶ + . . . + µ x t ¶ , (4.5) не является степенью линейного многочлена при t ≥ 2 (здесь правая часть равен- ства (4.5) является числом векторов в шаре радиуса t в x-мерном кубе E x ), где 4.4. Некоторые свойства совершенных кодов 45 d = 2t + 1 — кодовое расстояние. Тогда, согласно лемме 4, из равенства (4.5) получа- ем, что число f (n) имеет простой множитель, больший двух при n достаточно боль- шом, и, следовательно, не может быть равным степени двойки; значит, 2 n /f (n) 6= 2 k ни для какого k. Это означает, что граница Хэмминга не может быть достигнута и не существует совершенного кода длины n с расстоянием d. Докажем теорему от противного. Пусть f (x) = a(b + cx) t , (4.6) где a, b, c — некоторые рациональные числа. Вычислим f (0) из последнего соотноше- ния: f (0) = 1 = ab t , т. е. f (x) можно переписать в виде f (x) = (1 + r· x) t , (4.7) где r = c/b — рациональное число. Подставляя x = 1 в равенство (4.5), получаем f (1) = 1 + µ 1 1 ¶ = 2. С другой стороны, из представления (4.7) имеем f (1) = (1 + r) t . Таким образом, (1 + r) t = 2, откуда 1 + r = t √ 2 рационально. Это противоречие доказывает теорему. N 4.4.3. Верхняя оценка числа совершенных кодов К сожалению, имеется только верхняя оценка числа совершенных двоичных ко- дов, близкая к тривиальной, хотя доказательство этого факта далеко от тривиально- го и основано на одном важном свойстве совершенных кодов, к описанию которого приступим. Лемма 5 (Августинович С. В., 1995). Произвольный совершенный двоичный код длины n, содержащий нулевой вектор, однозначно определяется множеством своих кодовых слов веса (n − 1)/2. Доказательство. Как и прежде, обозначим все двоичные векторы веса k че- рез E n k и рассмотрим множество X n−1 2 = C ∩ E n n−1 2 всех кодовых слов веса (n − 1)/2 в совершенном коде C, содержащем 0 n . Прежде всего, следует заметить, что если известно множество X n−1 2 , то, согласно следствию 7, множество X n−1 2 является под- множеством кода C, где X n−1 2 — множество всех антиподальных слов множеству слов X n−1 2 . Пусть существует по крайней мере два продолжения множества X n−1 2 ∪ X n−1 2 до совершенных кодов: C = A ∪ X n−1 2 ∪ X n−1 2 ∪ A, (4.8) 46 Глава 4. Свитчинговые методы C 0 = B ∪ X n−1 2 ∪ X n−1 2 ∪ B, где A 6= B. C=A X X A U U U n+1 A X X A C =A X ’ X B U U U A X X B n 1 – 2 2 Рис. 7. Иллюстрация к предложению 5 Легко видно, что d(A, B) ≥ 3. Используя этот факт, можно построить совершен- ный код D = A ∪ X n−1 2 ∪ X n−1 2 ∪ B (4.9) (рис. 7). Из A 6= B имеем A 6= B и, следовательно, найдется вектор y ∈ B такой, что y / ∈ A. Отсюда, из соотношения 4.9 и свойства антиподальности совершенного кода (см. следствие 7), получаем y / ∈ A. Снова в силу антиподальности совершенного кода из равенства 4.9 имеем y ∈ D, следовательно, y ∈ A, противоречие. N Используя это свойство, можно доказать верхнюю оценку N n числа различных совершенных двоичных кодов длины n. Теорема 20 (Августинович С. В., 1995). Число N n различных совершенных двоичных кодов длины n удовлетворяет неравенству N n ≤ 2 2 n− 3 2 log n+log log(en) . Доказательство. Из леммы 5 легко получить следующую верхнюю оценку числа различных совершенных двоичных кодов длины n: N n ≤ µ |E n (n−1)/2 | |E n (n−1)/2 ∩ C n | ¶ . Используя дважды формулу Стирлинга n n e −n √ 2πn ≤ n! ≤ n n e 1−n √ 2πn и следствие 8, получаем N n ≤ à |E n (n−1)/2 | A n−1 2 ! ≤ µ 2 n / √ n 2 n /n √ n ¶ ≤ 2 2 n− 3 2 log n+log log(en) . (4.10) 4.4. Некоторые свойства совершенных кодов 47 Замечания 1. Сравнивая эту оценку с лучшей нижней оценкой числа различных совершен- ных двоичных кодов, убеждаемся в большом разрыве между ними. 2. Тривиальная верхняя оценка имеет вид 2 2 n−log n . Упражнение 20. Доказать, используя приведенный выше вариант формулы Стирлинга, неравенство µ n (n − 1)/2 ¶ ≤ 2 n √ n . Упражнение 21. Доказать, используя формулу Стирлинга, что число A n−1 2 из следствия 8 удовлетворяет неравенству A n−1 2 ≤ c 2 n n √ n , где c — некоторая константа. Упражнение 22. Доказать, используя формулу Стирлинга, неравенство (4.10). Упражнение 23. Доказать, что базовое множество кода Хэмминга, состоящее из кодовых слов веса 3, может быть построено индуктивно из представления кода Хэмминга посредством конструкции Васильева. Нерешенная проблема Найти новую верхнюю оценку числа различных совершенных двоичных кодов длины n ≥ 15. Глава 5 Каскадные методы 5.1. Основная идея каскадного способа построения Каскадный метод построения кодов впервые был предложен в 1966 г. Г. Д. Форни, затем, в начале 70-х гг., теория каскадных и обобщенных каскадных кодов была развита В. В. Зябловым, Э. Л. Блохом, В. А. Зиновьевым. Рассмотрим основную идею каскадного способа построения кодов. Пусть A является q-значным (n, |A|, d)-кодом, т. е. кодом длины n, мощности |A|, с кодовым расстоянием d. Пусть B — q 0 -значный (N, |B|, d 0 )-код, где |B| = q. Обозначим кодовые слова кода B следующим образом: B = {b(0), . . . , b(q − 1)}. Для любого кодового слова a = (a 1 , . . . , a n ) ∈ A построим вектор a(B) = ¡ b(a 1 )| . . . |b(a n ) ¢ , где символ | обозначает конкатенацию векторов. Множество C = {a(B) : a ∈ A} является q 0 -значным кодом. Легко найти параметры этого кода: длина равна nN , мощность — |C| = |A| и кодовое расстояние — d(C) ≥ dd 0 . Коды A, B и C называются, соответственно, внешним, внутренним и каскадным кодами. В этой главе будет приведено несколько каскадных методов построения кодов (иногда для простоты изложения рассматривается случай кодов с малыми кодовыми расстояниями), принадлежащих различным авторам. Сначала рассмотрим наиболее простые каскадные методы построения кодов, затем более сложные. В конце гла- вы изложим обобщенную каскадную конструкцию В. А. Зиновьева для нелинейных кодов (обобщенная каскадная конструкция для линейных кодов была предложена ранее В. В. Зябловым и Э. Л. Блохом). 5.2. Коды Соловьевой (1981) Для определения каскадной конструкции, предложенной Ф. И. Соловьевой в 1981 г., потребуются разбиения n-куба E n на совершенные коды. Разбиения E n на совершенные коды. Рассмотрим произвольный совершен- ный код C с кодовым расстоянием 3 длины n = 2 m −1 при m ≥ 2. Используя свойство плотной упакованности совершенного кода в E n , легко получить следующее триви- альное разбиение E n на аналоги классов смежности по совершенному коду C: E n = C ∪ (C + e 1 ) ∪ . . . ∪ (C + e n ), 48 5.2. Коды Соловьевой (1981) 49 где e i — вектор с единственной ненулевой координатой i. Приведем нетривиальную конструкцию широкого класса нетривиальных разбиений E n на совершенные коды для любой допустимой длины кода n > 7, используя конструкцию Васильева. Обо- значим этот класс через P n . Теорема 21 (Соловьева Ф. И., 1981). Существует класс P n различных раз- биений куба E n на совершенные коды длины n ≥ 15, где |P n | ≥ 2 2 (n−1)/2 . Доказательство проведем индукцией по m, где m = log(n + 1). Для m = 2 существует лишь тривиальное разбиение, поскольку для n = 3 су- ществует единственный совершенный код — это код Хэмминга H 3 . К. Т. Фелпсом показано, что при n = 7 существует 11 неэквивалентных разбиений E 7 на различные коды Хэмминга длины 7. Рассмотрим произвольное разбиение E (n−1)/2 , m − 1 = log((n + 1)/2), на совершен- ные коды длины (n − 1)/2: E (n−1)/2 = (n−1)/2 [ i=0 C (n−1)/2 i . Перейдем к случаю m. Используя конструкцию Васильева, из каждого кода C (n−1)/2 i , i ∈ {0, 1, . . . , (n − 1)/2}, построим следующие два совершенных кода длины n. Пер- вый код имеет вид C n i = {(x + y, |x| + λ i (y), x) : x ∈ E (n−1)/2 , y ∈ C (n−1)/2 i }, второй — C n i+(n+1)/2 = C n i + e (n+1)/2 , где, как и в конструкции Васильева, функция λ i является произвольной функцией из кода C (n−1)/2 i в множество {0, 1}. Легко показать, что любые два построенных кода не пересекаются. Число различных разбиений не меньше числа выборов различных функций λ i для каждого i = 0, 1, . . . , (n − 1)/2. Следовательно, |P n | ≥ ³ 2 |C (n−1)/2 i | ´ n+1 2 = µ 2 2(n+1)/2 n+1 ¶ n+1 2 = 2 2 (n−1)/2 , что завершает доказательство. N В дальнейшем в этой главе под совершенными кодами подразумеваются совер- шенные коды с расстоянием 3. 50 Глава 5. Каскадные методы Теорема 22 (Соловьева Ф. И., 1981). Пусть E n = n [ i=0 C n i , E n = n [ i=0 D n i произвольные разбиения куба E n на совершенные коды длины n и π — произвольная подстановка на множестве n + 1 координат. Тогда множество C = {(x, y, |y|) : x ∈ C n i , y ∈ D n π(i) , i = 0, 1, . . . , n} является совершенным двоичным кодом длины 2n + 1. Доказательство. Легко видеть, что длина кода равна 2n + 1 = 2 m+1 − 1, где n = 2 m − 1. Мощность кода равна |C| = (n + 1) · |C n i | · |D n i | = (n + 1) · |C n i | 2 = (n + 1) · 2 2n (n + 1) 2 = 2 2n+1 (2n + 1) + 1 . Проверим, что кодовое расстояние равно 3. Пусть u = (x, y, |y|) и v = (x 0 , y 0 , |y 0 |) — произвольные различные кодовые слова кода C. Возможны три случая. 1. Если x = x 0 , y 6= y 0 , x ∈ C n i , i = 0, 1, . . . , n то y, y 0 ∈ D n π(i) и d(y, y 0 ) ≥ 3, значит d(u, v) ≥ 3. 2. Случай x 6= x 0 , y = y 0 аналогичен предыдущему. 3a. Пусть x 6= x 0 , y 6= y 0 и x, x 0 ∈ C n i . Тогда d(x, x 0 ) ≥ 3 и, следовательно, d(u, v) ≥ 3. 3b. Пусть x 6= x 0 , y 6= y 0 и x ∈ C n i , x 0 ∈ C n j , где i, j ∈ {0, 1, . . . , n} и i 6= j. Тогда y ∈ D n π(i) и y 0 ∈ D n π(j) . Если |y| = |y 0 |, то d(y, y 0 ) ≥ 2, d(x, x 0 ) ≥ 1 и, значит, d(u, v) ≥ 3. При |y| 6= |y 0 | имеем d(y, y 0 ) ≥ 1, d((y, |y|), (y 0 , |y 0 |)) ≥ 2, d(x, x 0 ) ≥ 1 и снова d(u, v) ≥ 3. Теорема доказана. N Конструкция легко обобщается с помощью общей проверки на четность на случай расширенных совершенных кодов. Иллюстрацию к теореме 22 для случая, когда C i и D π(i) — расширенные коды, n = 2 m см. на рис. 8. E n C D Í E n C i D ð(i) i ð(i) Рис. 8. Случай расширенных кодов 5.3. Коды Романова 51 Замечания 1. Несложно показать, что эта конструкция является каскадной. 2. Конструкцию можно обобщить следующим образом: вместо двух разбиений пространства E n на совершенные коды рассмотреть разбиения двух различных кодов C 1 и C 2 на непересекающиеся подкоды с параметрами некоторых кодов C 3 и C 4 соответственно (см., например, теорему 63 в разд. 9.2.). В случае разбиений кодов C 1 и C 2 на смежные классы по кодам C 3 и C 4 (т. е. тривиальных разбиений) эта конструкция называется конструкцией X4 (см. [1, гл. 18]). 3. Следует отметить, что, используя эту конструкцию, можно построить класс разбиений E n на совершенные двоичные коды. 4. Класс совершенных кодов, описанный в этом разделе, не эквивалентен классу кодов Васильева. В 1984 г. К. Т. Фелпс обобщил эту конструкцию. В 2000 г. он доказал, что существует по крайней мере 963 и не более 15 408 неэквивалентных кодов Соловьевой длины 15. В 2004 г. В. А. Зиновьев и Д. В. Зиновьев доказали, что существует в точности 758 совершенных кодов длины 15 ранга 13. В 2006 г. С. А. Малюгин построил 55 совершенных кодов длины 15 ранга 15. Упражнение 24. Доказать, что C n i ∩ C n j = ∅ для любых i, j ∈ {1, 2, . . . , (n − 1)/2}, i 6= j в теореме 21. Упражнение 25. Построить класс разбиений куба E n на совершенные двоичные коды, используя теорему 22. Упражнение 26. Обобщить каскадную конструкцию теоремы 22 для расширен- ных совершенных кодов. |