А.В. Чашкин - Задачи с некоторых семинаров по дискретной математике, страница 3

, αit . Введем понятие многочлена локаторов ошибок.Выглядит эта зверюга вот так:σ(x) = (x − αi1 )(x − αi2 ) . . . (x − αit ) = xt + σ1 xt−1 + . . . + σt ,(3)Pгде σk — уже знакомый нам объект, σk = (−1)kαi1 . . . αik . Более того, про них нам известноследующее:i1 ,...,ikS1 + σ1 = 0 S3 + S2 σ1 + S1 σ2 + σ3 = 0. .. S2t−1 + S2t−2 σ1 + . .

. + St−1 σt = 0.8(4)Знакомьтесь: это линейная система. Чтобы лучше понять, что она из себя представляет, нампонадобятся две леммы.Лемма 1. Пусть Sj = α1j + . . . + αvj , v 6 t − 2. Тогда det Mt = 0, где100... 0 S2S11... 0 Mt = (5)....S2t−2 S2t−3 S2t−4 . . . St−1 Нетрудно заметить, что умножая матрицу Mt на (0, 1, σ1 , . . . , σt−2 )T получим нулевойстолбец. А это и означает, что det Mt = 0. Перейдем теперь собственно к алгоритму Питерсона. Он состоит из следующих шагов.1. Находим синдром S1 , .

. . , S2t .2. Считаем определитель det Mt . Если он оказался равен 0, делаем вывод: произошло меньшеt − 1 ошибок. В этом случае переходим к меньшей матрице Mt−2 и повторяем проверку.Как только для некоторого v получили det Mv > 0, переходим к следующему шагу.3. Решаем систему Mv (σ1 , . . . , σv )T = (S1 , . . .

, S2v−1 )T4. Ищем корни многочлена σ(x) и узнаем номера разрядов, в которых произошли ошибки.6. СФЭkЗадача 1. Задано k > 0 и функция F из B2 −1 в Bk . Действие функции определим с помощью матрицы H кода Хемминга следующим образом. Пусть x̄ = x1 , . . . , x2k −1 — входнойнабор, i1 , . . . , im — набор индексов, которым соответствуют номера единиц в j-й строке матрицы Хемминга; тогда j-я компонента вектора F (x̄) будет выглядеть следующим образом:xi1 & .

. . &xik . Далее (по вполне понятным причинам) мы будем записывать это равенствотакF (x̄) = H x̄.(1)На месте конъюнкций, разумеется, можно было бы поставить любую другую бинарную операцию – суть задачи от этого не изменится. А задача заключается в том, чтобы найтисложность СФЭ, реализующей такую функцию, над базисом {&}.Решение. Прежде всего, запишем матрицу Хемминга так, чтобы в столбцах стояли попорядку двоичные записи чисел 1, . . .

, 2k − 1, а слева еще припишем нулевой столбец:0 0 ... 0 0 1 1 ... 1 1 0 0 . . . 0 1 0 0 . . . 0 1Hk = (2)....0 1 ... 1 1 0 1 ... 1 1Несложно заметить, что имеет место представление0 ... 0 1 ... 1Hk =.Hk−1Hk−1(3)Итак, пусть hk — сложность схемы, реализующей Hk . Тогдаhk = hk−1 + (2k−1 − 1) + (2k−1 − 1),9(4)где второе слагаемое отвечает за склейку 2k−1 пар переменных, которые потом парами подаютсяна входы схемы для Hk−1 , а третье — за конъюнкцию последних 2k−1 переменных, соответствующую первой строке матрицы Hk .

Итак, окончательно получаемhk = 2k+1 − 2k.(5)Замечание. Здесь хорошо бы еще доказать, что ее нельзя реализовать меньшим числомэлементов. Пока что это доказательство откладывается до лучших времен. . .10.