У. Питерсон - Коды, исправляющие ошибки (1267328), страница 43
Текст из файла (страница 43)
Ниже указано содержимое накопителя Фнг. 7.12. Схема для счета в обратном направлении в поле Галуа. '1 См., например, работы Рнчардса 12541 и Гаванна [1311. после каждой операции. Заметим, что используется векторное сложение и символ ао помещается слева, Уст роислмо Сойе ржи мое умножения накопителя О1 0!СО)(Г) 0000 Сланение 1(010) 11 ! Р Ивие О!11 Сложение 0(1!10) 0111 Срвие 111 ! Сложение 1О ИО) 0001 ССвие ! 100 Сложение !(!!10) 0010 (Ответ) Кроме того, используя схему, приведенную на фиг.
7.6, можно вычислять значение многочлена г(Х) при Х, равном некоторому элементу поля а. Для этого в качестве многочлена д(Х) следует взять минимальную функцию для а. Представление в виде элемента поля Галуа для г (а) = г„,а" ' + г„-аа" ~ + ... + го может быть найдено исключением слагаемых, содержащих степени элемента а выше й, с использованием соотношения д(а) = О. Именно это и происходит, если в устройство, изображенное на фиг.
7.6, поступает вектор (го,гь ....г ~). Пример, Пусть и — примитивный элемент поля 6г (24), использованный для представления элементов поля в табл. 6.1. Представление в виде элемента поля Галуа для г(а) =г„-~а" '+ г„— ва" о+ ... +го может быть вычислено при помощи схемы, изображенной на фиг. 7.11, в которую поступает вектор (го, гь..., г,). Вычисление значений г(а!) для / Ф'1 (или О) значительно усложняется, если результат должен быть найден в виде много!лена от низших степеней а. Один из известных методов основан !а использовании регистра сдвига, автоматически производящего умножение на ай Для того чтобы разъяснить основные принципы !того метода, рассмотрим пример для 1= 5. Заметим, что в соответствии с табл. 6.1 1а'= а' = а'+ а, ацв цв=ав+ае, алас=а"=ав+ а+ 1, цза' =-а'- а'+ 1.
Фиг. 7.13. Схема лля умножения ня Х' я (77»(2»). 7.4. Линейные рекуррентные соотношения и генераторы с регистром сдвига Рассмотрим рекуррентпые соотношения, или разностные уравнения, и Х й(а,+1= 0 1 (7.2а) или ас+з= йгас+1» 1-О (7.2б) так что сР (а,аз + азсР + а,а+ ао) = аз (аз+ 1) + а (аз + а + 1) + + а, (сР + а9 + ао (а'+ а) = (ос + аз) и + (аз+ ас + аз) и + + (по+ аз) а+ (аз+ аз) Таким образом, новое значение ао равно прежнему значению суммы аз+ аз, новое значение а1 равно прежнему значению суммы аз+аз и т. д.
Регистр сдвига обратной связи, изображенный па фиг. 7.13, позволяет провести эти вычисления. Поэтому если полученный в результате передачи вектор («ы,..., «ь «о) последова. тельно подавать в это устройство, то после пятнадцати сдвигов содержимое регистра сдвига будет равно значению «(аз).
Другой способ вычисления «(Х») и представления его в виде многочлена от низших степеней а был предложен Цянем (49). Этот способ состоит в следующем. Многочлен «(Х») получают из много- члена «(Х), вставляя 1 — 1 нулей между последовательными степенями «(Х).
Значение этого нового многочлена прн Х = а может быть найдено при помощи схемы, изображенной на фиг. 7.б. Здесь используются несколько более простые схемы, чем при первом способе, однако требуется в 1 раз больше сдвигов. где йоФ О, Ьь = 1 и каждое Й! принадлежит полю еег(у). Решением этих уравнений является последовательность ао, аь ат, ... элементов поля бр(д). Соотношение (7.2б) определяет правило вычисления ад по заданным значениям величин аы аь ..., аь ь По известным значениям аь аь ..., аа можно найти аь+1 и т.
д. Поскольку уравнения линейны, то любая линейная комбинация их решений есть снова решение, а все решения образуют векторное пространство. Совокупность из тс решений, для каждого из которых один из символов ао, аь ..., аь 1 равен 1, а остальные равны О, порождает все пространство решений; следовательно, размерность пространства решений не превосходит я. Так как ао, аь ..., аь 1 произвольны, то размерность пространства равна по меньшей мере й. Таким образом, размерность пространства равна й.
На фиг. 7.14 изображена линейная последовательная переключательная схема, которая может быть использована для вычисления суммы (7.26) и, следовательно, для вычисления величины аь по значениям й предыдуШих членов последовательности. Исходные величины аы аь ..,, а„~ помешаются в разряды устройства, последовательные сдвиги которого соответствуют вычислению последовательных символов, и выход после 1-го сдвига равен аь Это устройство называется генератором с регистром сдвига. Решения линейных рекуррентных соотношений описываются следующей теоремой: Теорема 7.1. Пусть й (Х) = ) Ь!Х~, йс чь О, йа=1 и и — наи- т-о меньшее целое полозкительное число, для которого многочлен Х" — 1 делится на й (Х) .
Пусть, далее, д (Х) = (Х" — 1)/й (Х) . Тогда решения рекуррентных соотношений (7.2а) и Х й1а,+! = О !=о яериодичньс с периодом и, и совокупность, составленная из первых периодов всех возможных решений, рассматриваемых как Фиг. 7д4. Генератор с регистром сленга, многочлены по моду ио Х" — 1: а(Х)=аоХ" '+а,Х" + ... +ак аХ+а„„ совпадает с идеалом, порожденным многочленом д(Х) в алгебре многочленов по модулю Х" — 1. Заметим, что если при таком определении многочлена а(Х) элементы а<о аь ... вь<числяются в порядке возрастания номеров, то коэффициенты многочлена а(Х) вычисляются начиная с коэффициентов при степенях вь<си<их порядков в соответствии с тем, что было принято в равд.
7.1. Доказательство. Сначала будет показано, что если (а(Х)) принадлежит идеалу, порожденному многочленом д(Х), то последовательность периода и ао, ан ..., а„,„а„а„... (7.3) является решением уравнений (7.2а). Рассмотрим произведение (а (Х)) (й (ХИ = (с (Х)), где а(Х) —.— а,Х" '+а,Х" '+ ... +а„,Х+а„,, й(х)=й,х +3, <х — + ... +й, с(Х)=с„,Х" '+ с„оХ" ~+ ... + со. Используя равенство (6.8), находим, что при А (1(п — 1 с<=йоа„«+й<а„<+ ...
+Ьоа„,,+ы (7.4) а при 0~1 А с<="оао — «-+ а<во-<+ ° ° ° +?«а -<+ + Ь<+<ао+ А<+у<+ ... + Ььаь « (7.5) Из теоремы 6.12 следует, что если (а(Х)) принадлежит идеалу (к (Х)), то (а(Х) )(И(Х)) =- О и, следовательно, с< = О для любого 1. Теперь рассмотрим последовательность (7.3). В этой последовательности а; = а<+„для всех <) О.
Поэтому каждое из рекуррентных соотношений (?.2а) эквивалентно одному из равенств (7.4) и (7,6), и, следовательно, если (а(Х)) принадлежит идеалу, порожденному многочле~ом д(Х), то последовательность (7.3) является решением рекуррентпых соотношений (7.2). Поскольку степень многочлена д(Х) = (Х" — 1) <«(Х) равна и — й, то по теореме 6.11 размерность идеала (д(Х)) равна й. Она совпадает с размерностью пространства решений, откуда в соответствии с теоремой 2.9 следует, что идеал должен содержать всс решения.
Некоторые нз решений могут иметь период, меньший чем и, ио должны существовать и решения, для которых это неверно, В ча- стности, решение, получаемое из (д(Х)), имеет период, равный и. Вто можно показать следующим образом. Если период такого решения т меньше чем и, то, очевидно, и делится на лг и каждый блок из п символов состоит из и/пт повторяющихся блоков из гп символов. В этом случае должно выполняться равенство д(Х) =д(Х)(Х"- + Х"-"+ ... + Х" + 1) = = д(ХЦХ" — 1)7(Х вЂ” !). Тогда (Х" — !) (Х вЂ” !) = й (Х) д(Х) (Х"-') = й(Х) 7(Х) (Х" — 1) и (Х вЂ” !) =й(Х) 7(Х), что противоречит предположению о том, что и — наименьшее целое число, для которого многочлен Х" — 1 делится на й(Х).
Ч. т. д. Прилгер. Найдем период решений над полем Сгг" (2) разностного рравнения, соответствующего многочлену Ь (Х) = Х'+ Ха -1- Х -!- + 1 =(Х+ 1)т(Х'+Х+1). Многочлен Х'+ 1 делится па много- члены Хт+Х+1 и Х+1, однако для того, чтобы многочлен Х" + 1 делился на многочлены Ха+ Х+ 1 и (Х+ 1)т, необходимо выбрать и равным б. Следовательно, период решения должен быть равен б. Периоды некоторых решений будут меньше 6, но должно найтись по крайней мере одно решение периода, равного б. Многочлен, порождающий идеал, для которого получается такое решение, равен д(Х) = (Х' — 1)/г1(Х) = Хт+ Х+ 1 и соответствует решению 1 1 1 0 0 О. Другими решениями являются все векторы, образующие пространство строк матрицы 111000 011100 001110 (7.б) 000111 В частности, период суммы первых двух векторов 1 0 0 1 0 0 в действительности равен 3, а период суммы первых трех векторов 1 0 1 О 1 0 в действительности равен 2.
В качестве следующего примера па фиг. 7.15 показан двоичный генератор с регистром сдвига, соответствующим многочлену Фиг. 7Л5. Генератор с регистром сдвига для последовательностей максимальиой клины, й(Х) = Х'+ Х'+ Х'+ Х'+ 1. Это примитивный многочлен, и, следовательно, па него делится многочлен Хм' — 1; однако никакой другой многочлен Х" — 1 при любых меньших значениях и на й(Х) не делится.
Таким образом, период выходной последовательности регистра сдвига равен 255. Это максимально возможная длина для генератора с регистром сдвига, содержащим 8 разрядов. (Дальнейшие подробности см. в равд. 8.5.) Все сведения, существенные при изучении циклических кодов, в наиболее удобной форме содержатся в теореме 7.1. Более того, как было проиллюстрировано предыдущим примером, используя эту теорему, можно легко определить возможные периоды последовательностей для данного регистра сдвига.
Используя этот результат, можно легко также осуществить синтез регистров сдвига для последовательностей определенных периодов. Другие способы изучения линейных рекуррентных соотношений будут описаны кратко. Рассмотрим рекуррентное соотношение, соответствующее в смысле теоремы 7.1 многочлену Ь(Х). Пусть сг — любой корень многочлена Ь(Х), лежащий, вообще говоря, в расширении поля. Тогда последовательность 1, а, а~, аз, ..., (7.7) очевидно, удовлетворяет рекуррентному соотношению.
Поскольку рекуррентное соотношение линейно, то любая линейная комбинация последовательностей возрастающих степеней корней является решением я~ = у~а~ + узпз + ... + уьаь (7.8) где аь ам ..., ах — /г корней многочлена Ь(Х), а Уь Уь ..., Ух— произвольные постоянные величины. (Здесь предполагается, что все корпи различны.) Так как известно, что размерность пространства решений равна А и в соотношении (7.8) А произвольных постоянных, то в результате получается полная совокупность решений. Этот способ нахождения решений, конечно, аналогичен классическому методу решения линейных дифференциальных уравнений; более того, имеется близкая параллель с методом интегральных преобразований, причем корни многочлена 6(Х) играют роль корней характеристической функции или полюсов выходной функции обычной линейной системы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
