О.Б. Лупанов - Курс лекций по дискретной математике, страница 8

Аналогично, если единиц ровнодве — на i-м и j-м местах, то равенство Hx = 0 означает, что сумма i-го и j-го столбцов матрицы H равна нулю,то есть они попросту совпадают. Опять противоречие, которое и доказывает наше утверждение. Из общих свойств корректирующих кодов следует, что линейный код V , исправляющий t ошибок, имеетминимальное расстояние не меньше 2t + 1.2.3. Коды БЧХЗдесь мы тоже будем говорить о корректирующих линейных кодах и изучим более эффективные алгоритмыих построения.2.3.1. Эффективное построение корректирующих кодовЗдесь мы будем рассматривать двоичные коды, то есть K = F2 .Сначала приведём (тупой) алгоритм построения проверочной матрицы линейного кода с минимальным расстоянием не меньше заданного числа d.

Берём матрицу H (первоначально пустую) из r строк и n столбцов.Пусть её столбцы — h1 , . . . , hn . В качестве h1 берём любой ненулевой вектор. Дальше действуем по индукции:пусть мы уже знаем столбцы h1 , . . . , hi , среди которых любые d − 1 линейно независимы. Тогда покажем, чтовыполняется неравенство N := C1i + C2i + .

. . + Cd−2< 2r − 1. Что значит, что вектор hi+1 можно добавить к ужеiимеющимся так, чтобы сохранилось условие линейной независимости любых d − 1 векторов? Это значит, чтолинейная оболочка любых d − 2 векторов не должна исчерпывать всё пространство K r (без нуля). Очевидно,мощность линейной оболочки не больше количества всевозможных линейных комбинаций, а их всего ровно Nштук. Значит, при N < 2r − 1 заведомо (i + 1)-й вектор добавить можно.rСледствие 2.5 (Граница Варшамова – Гилберта). Если C0n−1 + C1n−1 + C2n−1 + .

. . + Cd−2n−1 < 2 , тосуществует матрица n × r, у которой любые d − 1 столбцов линейно независимы. Очевидным образом следует из алгоритма: если неравенство ещё не обратилось в равенство при n − 1столбце, то найдётся место и для n-го. 2.3.2. Построение поля из 2m элементовПоле Галуа F := GF (2m ) из 2m элементов строится как факторкольцо кольца многочленов F2 [x] по идеалу,порождённому неприводимым многочленом степени m. Это поле является m-мерным векторным пространствомнад полем F2 . Иногда мы будем рассматривать его элементы как многочлены степени меньше m над полем F2 ,а иногда — как наборы их коэффициентов, то есть m-мерные вектора из нулей и единиц.Напомним, что в поле характеристики p имеет место автоморфизм Фробениуса (a + b)p = ap + bp , так каквсе остальные биномиальные коэффициенты делятся на p и потому в этом поле равны нулю.

Применяя этуsssформулу несколько раз, получаем более общий факт: (a + b)p = ap + bp , и очевидно, что она верна и длянескольких слагаемых.2.3.3. Двоичные коды БЧХmПусть n = 2 − 1, и α1 , . . . , αn — все ненулевые элементы поля F . Через γi будем обозначать столбецкоэффициентов многочлена αi (то есть αi и γi — это разные записи одного и того же объекта).Рассмотрим матрицыγ1γ2...γnα1α2...αn γ13 α31α32...α3n γ23...γn3 H := (30)A :=  ··············· ·········γ12t−1 γ22t−1 . .

. γn2t−1 tm×nα2t−1α2t−1. . . α2t−1n12t×nОпределение. Кодом БЧХ (Боулз – Чоудхури – Хоквингем) называется код с проверочной матрицей H.Теорема 2.12. В матрице H любые 2t столбцов линейно независимы. Допустим, что это не так, и нашлись линейно зависимые столбцы hi1 , . .

. , hil , где l 6 2t. Тогда имеемS1 := αi1 + . . . + αil = 0,S3 := α3i1 + . . . + α3il = 0,···S2t−1 := α2t−1+ . . . + α2t−1= 0.i1il25(31)Покажем, что степенные суммы Sk с чётными номерами тоже равны нулю. Пусть k = 2s u, где u нечётно. Тогдаsв силу автоморфизма Фробениуса (Su )2 = Sk .

Значит, если Su = 0, то и Sk = 0.Таким образом, получаем, что Si = 0 при i = 1, . . . , l. Это «кусочек» матрицы Вандермонда, столбцы которойлинейно независимы, если все элементы αj различны (а в нашем случае это именно так). Противоречие. Тут ещё был очень малопонятный пример... для случая двух ошибок.2.4. Алгоритм Питерсона2.4.1. ТеорияЗдесь все рассуждения проводятся для произвольного поля F из q m элементов.Определение.

Пусть b — целое неотрицательное число, и пусть α ∈ F — примитивный корень n-й степенииз 1, где m является мультипликативным порядком числа q по модулю n. Тогда кодом БЧХ длины n с конструктивным расстоянием d, где 2 6 d 6 n, над полем F называется циклический код, определяемый корнямиαb , αb+1 , . . . , αb+d−2 порождающего многочлена g(x).Порождающая матрица кода с порождающим многочленом g(x), deg g(x) = n − k, имеет видg0 g1 . . . gn−k00 ...0 0 g0 g1. . . gn−k 0 .

. .0 .G=(32)...0 0 ...0g0g1 . . . gn−kЗамечание. До сих пор мы рассматривали случай b = 1 (БЧХ-код в узком смысле), n = q m −1 (примитивныйБЧХ-код) и, наконец, q = 2.Обозначим через w(x), v(x) и e(x) передаваемый кодовый многочлен, принимаемый многочлен и многочленошибок соответственно; тогда v(x) = w(x) + e(x). Прежде всего найдем синдром вектора v:S(v) = Hv T = (Sb , Sb+1 , .

. . , Sb+d−2 )T ,(33)Sj = v(αj ) = w(αj ) + e(αj ) = e(αj ), b 6 j 6 b + d − 2.(34)гдеЕсли имеется r 6 t ошибок, тоe(x) =rXci xai ,(35)i=1где a1 , . . . , ar — различные элементы из {0, . . . , n − 1}. Элементы ηi = αai ∈ F называются локаторами ошибки,а элементы ci ∈ Z∗q — значениями ошибки. Таким образом, для синдрома получаем формулуSj = e(αj ) =rXi=1а тогдаSjq=rXci ηiji=1!q=ci ηij , b 6 j 6 b + d − 2,(36)X(37)cqi ηijq =Xci ηijq = Sjq .В двоичном случае последняя формула — это формула для вычисления четных элементов синдрома.Нам надо найти неизвестные пары (ηi , ci ). В двоичном случае все ci могут принимать лишь значение,равное 1, поэтому искать их не нужно.Следующим шагом декодирующего алгоритма является нахождение коэффициентов σi , задаваемых так:rYi=1(ηi − x) =rX(−1)i σr−i xi .(38)i=0Таким образом, σ0 = 1, а σ1 , . .

. , σr — элементарные симметрические многочлены от η1 , . . . , ηr . Подставляяηi вместо x, получаем для всех i = 1, . . . , r:(−1)r σr + (−1)r−1 σr−1 ηi + . . . + (−1)σ1 ηir−1 + ηir = 0.(39)Умножим на ci ηij и просуммируем по всем i:(−1)r σr Sj + (−1)r−1 σr−1 Sj+1 + . . . + (−1)σ1 Sj+r−1 + Sj+r = 0,26(40)где j = b, b + 1, . . . , b + r − 1.Лемма 2.13.

Система уравненийrXi=1ci ηij = Sj , j = b, b + 1, . . . , b + r − 1,(41)относительно неизвестных ci разрешима, если ηi различны. Определитель этой системы есть определитель Вандермонда, умноженный на η1b · . . . · ηrb . Лемма 2.14. Система уравнений(−1)r σr Sj + (−1)r−1 σr−1 Sj+1 + .

. . + (−1)σ1 Sj+r−1 + Sj+r = 0,(42)где j = b, b + 1, . . . , b + r − 1 относительно неизвестных (−1)i σi однозначно разрешима тогда и только тогда,когда в полученном слове имеется ровно r ошибок. Матрица этой системы равна V DV T , где V — определитель Вандермонда от переменных ηi степениr − 1, а D — диагональная матрица с элементами вида ci ηib на главной диагонали.

Она невырождена тогда итолько тогда, когда невырождены V и D — то есть как раз когда имеется ровно r различных ошибок. 2.4.2. ПрактикаТеперь, наконец, можно перейти к самому алгоритму Питерсона. Итак:1◦ Находим синдром полученного словаS(v) = Hv T = (Sb , Sb+1 , . . . , Sb+d−2 )⊤ .ПустьSj =rXi=1ci ηij , b 6 j 6 b + d − 2.(43)(44)2◦ Находим максимальное число r 6 t, такое, что система уравнений(−1)r σr Sj + (−1)r−1 σr−1 Sj+1 + . . .

+ (−1)σ1 Sj+r−1 + Sj+r = 0,(45)где j = b, b + 1, . . . , b + r − 1 относительно неизвестных (−1)i σi имеет невырожденную матрицу коэффициентов. Тем самым получаем число появившихся ошибок. Построим многочлен локаторов ошибки:s(x) =rYi=1(1 − ηi x) =rXσi xi .(46)i=0Коэффициенты σi выражаем через Sj .3 Решаем уравнение s(x) = 0 и находим локаторы ошибки ηi . В двоичном случае на этом всё заканчивается.4◦ Подставляя ηi в системуrXSj =ci ηij , b 6 j 6 b + d − 2,(47)◦i=1полученную на 1-м шаге, находим значения ошибки ci .3.

Схемы из функциональных элементовПри работе с булевыми функциями мы иногда будем заменять значок & обычной точкой (произведением)или не писать его вовсе.3.1. Схемы из функциональных элементовОпределение. Схема из функциональных элементов (СФЭ) — это конечный ориентированный граф безориентированных циклов, в каждую вершину которого входит не более 2 рёбер. При этом каждой вершине приписывается символ: переменная xi , если в эту вершину рёбра не входят; отрицание, если в вершину входит одноребро; конъюнкция или дизъюнкция, если в вершину входит 2 ребра. Некоторым вершинам приписывается ∗.Элементами схемы называются вершины, помеченные логическими операциями.27Занумеруем вершины графа согласно теореме 1.16.

Каждой вершине СФЭ можно сопоставить некоторуюбулеву функцию по следующему индуктивному правилу. Пусть всем вершинам с номерами меньше n уже сопоставлены функции. Возьмём вершину с номером n. Если в неё не входит ни одного ребра, то ей приписанапеременная, которую мы как функцию и поставим ей в соответствие.

Если в вершину входит одно ребро, тов ней записано отрицание, и мы припишем этой вершине отрицание функции той вершины, из которой в данную вершину приходит ребро. Если входит два ребра, то в этой вершине будет конъюнкция или дизъюнкцияфункций тех вершин, из которых приходят эти рёбра. Видно, что такое определение корректно.Определение. Функции, отвечающие вершинам, отмеченным ∗, называются реализуемыми данной СФЭ.x11x22∨ 43 &5 ¬&6∗Рис. 9. Пример СФЭПример 1.1.

Приведённая на рис. 9 схема реализует функцию (x1 ∨ x2 ) & (x1 & x2 ) = x1 ⊕ x2 .Существует физическая интерпретация СФЭ, в которой они рассматриваются как математические моделисоответствующих реальных электронных схем: если на вход подаётся набор значений (наличие тока соответствует единице, отсутствие — нулю), то на выходе получается значение функции на этом наборе.Определение.

Сложностью схемы S называется число элементов L(S) в ней. Сложностью функции fназывается минимальная сложность схемы для f . Функция Шеннона L(n) выражает максимальную сложностьфункций от n переменных.Построим СФЭ, реализующую функцию f = xσ1 1 · . . .