Теория, методы и алгоритмы решения задач в телекоммуникациях на основе двойственного базиса и рекуррентных последовательностей тема диссертации и автореферата по ВАК РФ 05.12.13, доктор технических наук Когновицкий, Олег Станиславович

• Когновицкий, Олег Станиславович
• доктор технических наук
• 2011

Оглавление диссертации доктор технических наук Когновицкий, Олег Станиславович

Введение.

ЧАСТЫ. ТЕОРЕТИЧЕСКИЕ И РЕАЛИЗАЦИОННЫЕ ОСНОВЫ РЕШЕНИЯ МОДУЛЯРНЫХ РАЗНОСТНЫХ УРАВНЕНИЙ ОДНОРОДНЫХ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

1. Линейные рекуррентные последовательности над конечным полем СР(р) и их особенности.

1.1. Определение и основные свойства линейных рекуррентных последовательностей.

1.2. Рекуррентные последовательности максимального периода (М-последовательности) над полем СР(р) и их свойства.

1.3. Формирование линейных рекуррентных последовательностей.

2. Аналитическое решение линейных модулярных возвратных уравнений над конечным полем.

2.1. Решение однородных линейных МРУ на основе г-преобразова-ния над конечным полем.

2.2. Двойственный базис конечного поля и его применение для решения однородных линейных МРУ.

2.3. Матричный метод решения линейных возвратных уравнений над полем 6Р(рк) по к произвольным линейно-независимым элементам рекуррентной последовательности.

2.4. Сравнение предложенных вариантов решения линейных МРУ.

3. Составные рекуррентные последовательности над полем GF(pk) с приводимым характеристическим многочленом и их обработка с использованием двойственного базиса.

3.1. , Последовательности Гоулда и их свойства.

3.1.1. Класс «зеркальных» последовательностей Гоулда.

3.2. ЛРД-последовательности и их свойства.

3.3. Решение линейных уравнений составных рекуррентных последовательностей над полем ОР (рк) на основе двойственного базиса.

3.4. Обработка последовательностей Гоулда и ЛРД-последователь-ностей.

3.4.1. Алгоритм быстрого поиска ЛРД-последовательности.

3.4.2. Обработка последовательностей Гоулда и составных ЛРД-пос-ледовательностей с использо-ванием двойственного базиса поля вР(2").

3.5. Прямые и инверсные рекуррентные последовательности.

4. Основы реализации алгоритмов обработки рекуррентных последовательностей над полем

4.1. Матричное представление элементов поля вР^).

4.2. Генераторы элементов поля бР(рк).

4.2.1. Генерация прямых элементов поля.

4.2.2. Генерация обратных элементов поля

4.3. Реализация умножения и деления элементов поля

4.3.1. Матричный способ умножения элементов поля.

4.3.2. Деление элементов поля через операцию обращения делителя и матричное умножение.

4.4. Способы обращения элементов поля ЗР(2к).

4.4.1. Нахождение обратного элемента через умножение "сопряженных" элементов.

4.4.2. Нахождение обратного элемента обращением сопровождающей матрицы.

4.4.3. Определение обратного элемента на основе двух модульных регистров.

4.5. Реализация процедуры нахождения функции следа.

4.6. Использование операций логарифмирования и антилогарифмирования при выполнении действий над элементами поля СГ(рк).

4.6.1. Умножение, деление и обращение элементов поля с использованием операций логарифмирования и антилогарифмирования.

4.6.2. Табличные алгоритмы реализации операций логарифмирования и антилогарифмирования над элементами поля GF(pk).

4.6.3. Аналитический метод реализации операций логарифмирования и антилогарифмирования над элементами поля GF(2k).

4.7. Формирование, линейных рекуррентных последова-тельностей на примере М-последовательностей.

4.7.1. Генератор М-последовательности на основе простого рекуррентного регистра сдвига с обратными связями.

4.7.2. Генератор М-последовательности на основе модульного регистра сдвига. Каноническая М-последовательность.

4.7.3. Формирование недвоичных М-последовательностей.

4.8. Формирование двойственного базиса поля.

4.9. Преобразование элементов поля GF(pk) в соответствующие элементы линейной рекуррентной последовательности и обратное преобразование.

4.10. Алгоритм упрощенной реализации умножения на двоичную матрицу над полем GF(2k)

ЧАСТЬ 2. ПРИМЕНЕНИЕ ДВОЙСТВЕННОГО БАЗИСА В ЗАДАЧАХ ПЕРЕДАЧИ И ОБРАБОТКИ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

5. Алгоритмы декодирования комбинаций эвидистантного циклического кода.

5.1. Декодирование эквидистантных циклических кодов методом корреляционной обработки.

5.2. Мажоритарная обработка рекуррентных последовательностей максимальной длины на основе ортогональных проверок.

5.3. Мажоритарные алгоритмы декодирования комбинаций эквидистантного циклического кода по k-элементным участкам.

5.3.1. Матричное мажоритарное декодирование комбинаций эквидистантного циклического кода.

5.3.2. Мажоритарное декодирование комбинаций эквидистантного циклического кода по k-элементным участкам на основе двойственного базиса GF(pk).

5.3.3. Декодирование децимированных комбинаций эквидистантного циклического кода с использо-ванием двойственного базиса поля GF(p^).

5.4. Декодирование комбинаций эквидистантного циклического кода по к произвольным линейно независимым ее элементам.

5.5. Эквидистантный циклический код (М-последовательность) в конечных полях с двойным расширением.

6. Декодирование дуальных циклических кодов БЧХ и Рида-Соломона, как рекуррентных последовательностей, с использованием двойственного базиса.

6.1. Декодирование кодов БЧХЭ на основе многочленов Мэттсона-Соломона.

6.2. Циклические коды БЧХЭ и их декодирование с использованием двойственного базиса.

6.3. Мажоритарное декодирование децимированных комбинаций кода БЧХЭ над полем GF(2k) на основе m-элементных участков с использованием двойственного базиса.

6.4. Принципы реализации кодирующих и декодирующих устройств кодов БЧХЭ как рекуррентных последовательностей.

6.5. Дуальные коды Рида-Соломона как рекуррентные последовательности и их декодирование с использованием двойственного базиса.

6.6. Укороченные циклические коды как рекуррентные последовательности.

7. Применение двойственного базиса поля GF(pk) в задачах циклового фазирования.

7.1. Поиск рекуррентной последовательности в асинхронных системах передачи данных методом последовательного оценивания.

7.1.1. Рекуррентный поиск по методу Уорда и его анализ.

7.1.2. Рекуррентный поиск с решением по «скользящему» зачетному участку и его анализ.

7.1.3. Обнаружение М-последовательности как фазирующей комбинации методом последовательного оценивания с использованием двойственного базиса.

7.1.4. Обнаружение последовательностей Гоулда или ЛРД-после-довательностей как фазирующих комбинаций в асинхронных системах с использованием двойственного базиса.

7.2. Цикловое фазирование в синхронных системах передачи данных.

7.2.1. Использование двойственного базиса для обработки /с-эле-ментных участков М-последовательностей как комбинаций циклового фазирования в синхронных системах передачи данных.

7.2.2. Обработка последовательностей Гоулда и ЛРД-последователь-ностей как фазирующих комбинаций в синхронных системах передачи данных с использованием двойственного базиса.

7.2.3. Цикловое фазирование приемника синхронной системы по к произвольным линейно независимым элементам М-последовательности

7.2.3.1. Цикловое фазирование по к произвольным линейно независимым элементам М-последовательности на базе рекуррентного регистра.

7.2.3.2. Цикловое фазирование по к произвольным линейно независимым элементам М-последовательности на базе модулярного регистра.

7.2.3.3. Фазирование дескремблера в АТМ-сетях.

7.3. Цикловое фазирование с несколькими ступенями обнаружения

8. Применение двойственного базиса в специальных задачах

8.1. Применение двойственного базиса для обработки линейной рекуррентной последовательности при измерении дальности до объекта.

8.2. Применение двойственного базиса в системах с относительным изменением фазы рекуррентной последовательности с «незакрепленной» начальной фазовой точкой.

8.3. Применение двойственного базиса для выделения адресных рекуррентных последовательностей.

8.4. Оценка качества каналов передачи данных на базе рекуррентных последовательностей.

8.4.1. Оценка качества каналов передачи данных в синхронных системах со сбоями цикловой фазы.

8.4.2. Возможность построения адаптивной системы передачи данных на основе применения двойственного базиса.

9. Применение двойственного базиса для анализа и обработки числовых рекуррентных рядов.

9.1. Использование двойственного базиса для анализа числовых рекуррентных последовательностей, удовлетворяющих уравнению «золотой пропорции» второго порядка.

9.1.1. Обобщенные числа Фибоначчи (по Люка).

9.1.2. Классическая последовательность чисел Фибоначчи.

9.1.3. «Смещённая» последовательность чисел Фибоначчи.

9.1.4. Последовательности Люка.

9.2. Свойства обобщённых последовательностей чисел Фибоначчи (по Люка), удовлетворяющих характеристическому уравнению «золотой пропорции» второго порядка.

9.3. Обобщённые р-числа Фибоначчи (по А.П. Стахову) и их анализ с помощью двойственного базиса.

9.4. Рекурсивные числовые последовательности и их анализ с помощью двойственного базиса.

9.5. Проблемы помехоустойчивого кодирования с использованием чисел Фибоначчи.

Введение диссертации (часть автореферата) на тему «Теория, методы и алгоритмы решения задач в телекоммуникациях на основе двойственного базиса и рекуррентных последовательностей»

В телекоммуникациях и информационных системах широкое применение находят рекуррентные последовательности над конечными полями. Особенностью таких последовательностей является то, что каждый ее член легко определяется по предшествующим ему членам на основе определенной рекуррентной зависимости. Наибольший интерес вызывают линейные рекуррентные последовательности (ЛРП), которые широко применяются в теории кодирования, а также в других прикладных задачах телекоммуникаций и информационных технологий.

Теория линейных рекуррентных последовательностей имеет уже более, чем восьмисотлетнюю давность. Считается, что первой в истории математики рекуррентной формулой является формула, полученная знаменитым итальянским математиком Леонардо из Пизы, известного по прозвищу Фибоначчи. Как известно, эту формулу он получил при решении «задачи о размножении кроликов». За всю дальнейшую свою историю интерес к рекуррентным последовательностям то затухал, то вновь возникал с новой силой. Так как члены рекуррентной последовательности линейным образом зависят от предыдущих, то их стали называть линейными рекуррентными (iвозвратными) последовательностями (ЛРП). Учитывая многие полезные свойства ЛРП они стали широко применяться в различных системах связи. Но наибольший интерес к линейным рекуррентным последовательностям над конечными полями стали проявлять с 50-х годов XX века в связи с интенсивными работами в области теории помехоустойчивого кодирования. Этому способствовал тот факт, что была установлена тесная взаимосвязь между теорией кодирования и линейными рекуррентными последовательностями и регистрами сдвига с обратной связью (РСОС).

Довольно полный обзор по этой тематике можно найти в энциклопедическом двухтомнике в русском переводе Р. Лидла и Г. Нидеррайтера «Конечные поля» [3]. Наибольшее количество работ как зарубежных, так и отечественных авторов посвящено теории линейных рекуррентных последовательностей над конечными полями. Среди этих авторов наиболее заметный вклад в развитие теории рекуррентных последовательностей внесли Р. Диксон (R. Dixon) [30], М. Уорд (М. Ward) [39], Н. Цирлер (N. Zierler) [25], Б. Элспас (В. Elspas) [38] и другие. Среди отечественных авторов, внесших заметный вклад в теорию рекуррентных (шумоподобных) последовательностей над конечными полями, следует отметить труды Л. Е. Варакина [27], P.P. Варшамова [41], Э. М. Габидулина [6], А. И. Маркушевича [И], А. А. Нечаева [103], В.И. Нечаева [102], В. Б. Пестрякова [32], Н. Т. Петровича [34], А. И. Алексеева [33] и др.

Взаимосвязи между линейными рекуррентными последовательностями и регистрами сдвига с обратной связью (переключательными схемами) посвящены работы С. Голомба (S. Golomb) [51,52], Р. Лидла и Г. Нидеррайтера (R. Lidl, Н. Niederreiter) [3], У. Питерсона (W. Peterson) [54], Б.

Элспаса (В. Eispas) [38], H. Цирлера (N. Zierler) [25], Ю.Л. Сагаловича [56], А.Н. Радченко и В.И. Филиппова [104], Р.Г. Фараджева [10] и других ученых.

Теория линейных рекуррентных последовательностей имеет важное применение также в теории помехоустойчивых кодов, особенно циклических. Основополагающими работами в этом важном направлении являются работы Э. Берлекэмпа (Е. Berlekamp) [5], Р. Галагера (R. Gallager) [106], Ф. Дж. Мак-Вильямса и Н. Дж. А. Слоэна (F.J. Mac Williams and N.J. А. Sloane) [2], P.K. Боуза и Д.К. Рой-Чоудхури (R.C. Bose and D.K. Ray-Chaudhuri) [105],. И. С. Рида (I. S. Reed) [108], Г. Соломона (G. Solomon) [12], Д. Хаффмена (D. Huffman), Т. Касами (T. Kasami) [1], Дж. Кларка, мл., и Дж. Кейна (G. Clark, Jr., and J Cain) [26], X. Мэттсона и Г. Соломона (H. Mattson and G. Solomon) [43], Дж. Месси (J. Messey) [24], У. Питерсона (W. Peterson) и Э. Уэлдона (Е. Weldon) [4,54], Э.М. Габидулина и В.Б. Афанасьева [6], P.P. Варшамова [109], В.М. Сидельникова, A.A. Нечаева и других ученых.

В большинстве работ исследователи уделяют основное внимание рекуррентным последовательностям максимального периода, называемым также М-последовательностями или псевдослучайными. Глубокое исследование таких последовательностей было проведено в работах С. Голомба (S. Golomb) [51,52], H. Цирлера (N. Zierler) [25], Б. Элспаса [38], JI.E. Варакина [27], В.Б. Пестрякова [32], Н.Т. Петровича [34], А.И. Алексеева [33] и других авторов. Последовательности максимального периода, имеющие хорошие корреляционные свойства, находят широкое применение в различных приложениях, в частности, для циклового (покадрового) фазирования, для измерения дальности до объкта в качестве дальномерного кода, в качестве адресных последовательностей в системах с множественным доступом. Этим вопросам посвящены работы Р. Диксона (R. Dixon) [30], Дж. Спилкера (J. Spilker) [72], В.И. Журавлев [31], В.В. Лосева [18 — 21]и других специалистов.

Для обеспечения требуемой достоверности при передаче данных по каналам с большой вероятностью ошибки по битам Qco>0,01) М-последовательности используются как комбинации эквидистантного циклического кода.

Во многих системах передачи данных для предотвращения появления длинных серий 1 или 0 используют специальные способы рандомизации потока. Наиболее часто для этого применяют скремблирование, при этом в качестве скремблирующей последовательности используют М-последовательности. Скремблирование позволяет улучшить качество работы устройств тактовой синхронизации. Одновременно с этим скремблирование выступает как средство криптографической защиты передаваемых данных[ ]. Связь скремблирования с псевдослучайными последовательностями и регистрами сдвига с обратной связью рассматривается в фундаментальной работе Дж. Спилкера (J. Spilker) [72].

Псевдослучайные рекуррентные последовательности широко применяют для расширения спектра. Этот метод в литературе назван методом прямой последовательности (DS— direct sequencing).

В ряде систем линейные рекуррентные последовательности используются в качестве адресов, при этом идентификация осуществляется по значению фазы выделенной последовательности.

Наконец, линейные рекуррентные последовательности применяют в качестве тестовых для выявления ошибок в каналах передачи данных.

Таким образом, линейные рекуррентные последовательности (М-последовательности) ввиду многих их полезных свойств находят широкое применение в различных телекоммуникационных системах. Тем не менее во многих случаях применяют составные рекуррентные последовательности, обладающие некоторыми специфическими свойствами, которые делают их более предпочтительными по сравнению с М-последовательностями. Примерами таких составных рекуррентных последовательностей являются так называемые дальномерные коды Лаборатории Реактивного Движения (ЛРД-коды) и коды Гоулда. Эти последовательности довольно подробно представлены в работах Р. Диксона (R. Dixon) [30] и Дж. Спилкера (J. Spilker) [72].

Применение рекуррентных последовательностей ставит перед разработчиками систем связи задачи по рациональному выбору как способов генерирования так и способов обработки таких последовательностей. Если задача формирования рекуррентных последовательностей однозначно решена на базе регистров сдвига с обратной связью, то задача обработки рекуррентных последовательностей решается по-разному, в зависимости от поставленных перед системой требований. При этом говорят об эффективности того или иного метода или алгоритма обработки. В качестве показателей эффективности чаще всего используют:

• надёжность или достоверность выделения (декодирования) рекуррентной последовательности;

• временные задержки, вызванные поиском и обработкой рекуррентной последовательности;

• сложность реализации алгоритмов поиска и обработки последовательностей.

Другими словами, показателями эффективности того или иного метода обработки являются традиционные вероятностно-временные характеристики и сложность реализации. Однако построение систем связи, использующих рекуррентные последовательности, как правило связано с преодолением противоречий. А именно, выбор одного главного показателя, по которому следует получить наилучшие результаты, приводит зачастую к тому, что остальные показатели могут быть ухудшены за счет улучшения главного показателя. Поэтому выбор того или иного алгоритма обработки рекуррентных последовательностей, как правило, направлен на улучшение главного показателя. Тем не менее, разработчики, стремящиеся получить наибольшую выгоду от реализации своего продукта, всегда пытаются найти способы улучшения главного показателя, не снижая или несущественно снижая другие показатели. Эта тенденция проявляется и при выборе алгоритмов поиска и обработки линейных рекуррентных последовательностей.

В большинстве случаев задача приемника состоит в обработке рекуррентной последовательности с целью её идентификации. При этом решение этой задачи во многом будет определяться длиной рекуррентных последовательностей и их количеством. Например, для выделения короткой рекуррентной последовательности в качестве фазирующей чаще всего применяют согласованный фильтр. Но для обеспечения высокой помехоустойчивости длина последовательности должна быть большой, что приводит к увеличению так называемых накладных расходов и делает систему более сложной. В случае использования рекуррентных последовательностей в качестве адресных чаще всего применяют также корреляционные методы, например, согласованные фильтры. При этом последовательности должны выбираться такими, чтобы между ними была малая взаимная корреляция, в противном случае усиление корреляции приводит к снижению помехоустойчивости. В приемнике для определения адреса отправителя в такой системе при аппаратной реализации необходимо установить количество согласованных фильтров по числу используемых рекуррентных последовательностей, что приводит к усложнению оборудования и увеличению его стоимости.

Каждая из используемых рекуррентных последовательностей может быть задана своей начальной фазой. Таким образом, для выделения той или иной адресной рекуррентной последовательности достаточно определить её фазу. Аналогом согласованных фильтров при программной реализации является алгоритм обработки с помощью циркулянтной матрицы Б, состоящей из всех различных рекуррентных последовательностей длины N каждая. Примем, что матрица 8 имеет вид: а принятую рекуррентную последовательность, в общем случае с ошибками, обозначим как вектор-столбец Х=(хо, хь хг,., хм.\ )Т. При этом обработка, которая считается оптимальной в смысле достоверности, заключается в вычислении вектора Г = ЗХ = (у0, уи у2,- ■ уы-\) и определении номера / компоненты^-, для которой значение убудет максимальным. Этот алгоритм реализует принцип максимального правдоподобия. Вычислительная сложность такого прямого матричного умножения составляет операций умножения и N(N—1) операций сложения, где N - длина рекуррентной последовательности. Поэтому такой алгоритм, с одной стороны, обеспечивает, как оптимальный, высокую достоверность, но, с другой стороны, имеет при длинных последовательностях большую вычислительную сложность, что ограничивает его применение.

В работах В.В Лосева [13], В.Г. Стародубцева и O.A. Павлова [111] показано, что указанная выше матрица-циркулянт S путем перестановок строк и столбцов может быть преобразована к виду, допускающему алгоритмы быстрого преобразования Уолгиа-Адамара. При этом такая факторизация матрицы S преобразует её в произведение слабо заполненных матриц, что позволяет сократить число требуемых операций при умножении вектор-столбца на факторизованную матрицу. Так, например, число операций умножения будет сокращено до N log2iV.

Некоторого упрощения можно достичь не путем перестановок строк и столбцов циркулянтной матрицы, а путем перестановок элементов входной и соответствующих обратных перестановок выходной последовательностей.

Но, несмотря на некоторое снижение вычислительной сложности, упомянутые выше алгоритмы не находят широкого применения ввиду того, что анализ рекуррентной последовательности на приемной стороне может начаться только после полного её приема. В случае рекуррентных последовательностей с чрезвычайно большими периодами такие алгоритмы прямого их поиска могут привести к недопустимо большому времени обнаружения и обработки искомой последовательности. Поэтому многие исследователи предлагают другие алгоритмы поиска и обработки рекуррентных последовательностей, которые, за счёт незначительного снижения достоверности, обеспечивают выигрыш в сложности реализации либо в скорости поиска и обработки последовательностей. К таким алгоритмам следует отнести, прежде всего, описанные в работах Дж. Спилкера, В.В. Лосева и др. корреляционные методы поиска и декодирования рекуррентной последовательности по относительно коротким её отрезкам. При этом решение выносится по значению взаимной корреляции между опорной и отрезками принимаемой последовательности. В этом случае снижается помехоустойчивость, но одновременно уменьшается время поиска и в некоторой степени снижается вычислительная сложность алгоритма. Тем не менее, такие алгоритмы позволяют компенсировать потери достоверности за счет применения мажоритарных методов принятия решения «по большинству».

К простым в реализации алгоритмам с мажоритарным декодированием относятся алгоритмы порогового декодирования на основе ортогональных проверок. Исследованию таких предельно простых алгоритмов посвящены работы Дж. Месси [24]. Достоинством мажоритарного декодирования является то, что система ортогональных проверок для символа (для М-последовательностей и блочных циклических кодов) переходит в такую же систему ортогональных проверок для следующего символа а(+\. Поэтому для посимвольного декодирования может быть использована одна и та же схема.

Развитием работ по пороговому декодированию на основе ортогональных проверок являются работы В.В. Золотарева [23], посвященные алгоритмам мажоритарного многопорогового декодирования. Главным достоинством этих алгоритмов является высокая степень достоверности, достигаемая благодаря применению итеративных процедур декодирования. Однако общим недостатком пороговых алгоритмов, как и многих других, является то, что декодирование начинается только после приема всей последовательности. Это, а также применение итераций приводит к увеличению задержек декодирования.

Для устранения указанного недостатка, т.е. для снижения задержек в обнаружении и обработке рекуррентных последовательностей, прежде всего М-последовательностей, стали использовать свойство рекуррентности принимаемой последовательности. Впервые это свойство было использовано Р. Уордом (R. Ward) [39] для быстрой синхронизации путем последовательной оценки. Частным случаем поиска рекуррентной последовательности методом последовательного оценивания является поиск по безошибочному зачетному отрезку последовательности. Метод последовательного оценивания рекуррентной последовательности имеет очень простую реализацию и обеспечивает быстрый поиск и вхождение в синхронизм, но его существенный недостаток — высокая чувствительность к помехам. Последнее определяется тем, что при декодировании не учитываются потенциальные возможности всей рекуррентной последовательности, решение принимается только по отдельным её отрезкам. Другим также существенным недостатком является то, что решающая схема оценивает принимаемую последовательность только на рекуррентность, т.е. эти методы в процессе проверки на рекуррентность не позволяют идентифицировать значение фазы обнаруженной рекуррентной последовательности. По этой причине метод последовательного оценивания может применяться только в системах цикловой синхронизации, где используется одна рекуррентная фазирующая последовательность заданной структуры.

Другие алгоритмы, позволяющие уменьшить время поиска и обработки рекуррентной последовательности корреляционными методами, основаны на применении составных рекуррентных последовательностей. Составные рекуррентные последовательности и их свойства достаточно полно описаны в работах Дж. Спилкера [72] и Р.К. Диксона [30]. Они формируются сложением по модулю 2 двух и более М-последовательностей. К ним относятся последовательности Гоулда и ЛРД-последовательности. Период составной рекуррентной последовательности равен наименьшему общему кратному периодов складываемых последовательностей.

Для формирования очень длинных составных рекуррентных последовательностей периоды составляющих М-последовательностей выбирают взаимно простыми. Тогда период составной последовательности будет равен произведению периодов составляющих её М-последовательностей. К таким составным последовательностям может быть применен алгоритм быстрого поиска, который основан на корреляционных связях составной последовательности с её составляющими М-последовательностями. При этом, чтобы составная рекуррентная последовательность была пригодна для быстрого обнаружения, необходима сильная взаимная корреляция между составной последовательностью и её составляющими М-последовательностями. Именно таким условиям удовлетворяют последовательности Лаборатории Реактивного Движения (ЛРД-последовательности), применяемые, в частности, в качестве дальномерных кодов. Если составная последовательность формируется путем сложения к М-последовательностей, периоды которых взаимно простые и равны Р, , то период составной последовательности будет равен к Таким образом, в случае прямого поиска составной 1 к последовательности по значению функции корреляции потребуется 1 кодовых элементов. В случае применения алгоритма быстрого поиска с последовательной идентификацией составляющих М-последовательностей к для поиска составной последовательности потребуется как минимум ^Pt 1 кодовых элементов, что может существенно уменьшить время поиска. Если же поиск и захват составной рекуррентной последовательности осуществлять с помощью к параллельно работающих корреляторов, то минимальное время поиска будет пропорционально периоду самой длинной составляющей М-последовательности. Таким образом, для уменьшения времени корреляционного поиска составной последовательности следует выбирать как можно меньше периоды составляющих М-последовательностей. Однако это приводит к снижению помехоустойчивости. Поэтому актуальной остается задача разработки новых алгоритмов, обеспечивающих малое время поиска при удовлетворении требований по достоверности. К числу таких алгоритмов можно отнести алгоритмы, допускающие мажоритарное декодирование не после завершения приема всей рекуррентной последовательности, а в процессе последовательного её приема. При этом можно ожидать простой реализации, как в методе последовательного оценивания, высокой достоверности за счет применения мажоритарных методов и быстрого поиска за счет обработки отдельных отрезков последовательности.

Разработка таких алгоритмов стала возможна после опубликования в 60-х годах XX в. результатов фундаментальных работ X. Маттсона (H.Mattson) и Г. Соломона (G. Solomon) [43] и представленных также в энциклопедическом двухтомнике известных математиков Р. Лидла и Г. Нидеррайтера (R. Lidl and Н. Niederreiter) [3]. Суть полученных результатов в этих работах сформулирована в виде леммы (теоремы), утверждающей следующее: если характеристический многочлен Р(х) = хк + р{хк~х +.+рк, соответствующий рекуррентной последовательности s^s^s^s^,. над простым полем GF(2), не имеет кратных корней, то существуют единственным образом определенные элементы cl;c2,.,ck из расширенного поля GF{ 2k), такие, что п=0,1,2,.), (В1)

1=1 где еу,.,ек - корнимногочлена Р(х).

Таким образом, произвольный член sn рекуррентной последовательности может быть определен через корни характеристического многочлена Р(х) и коэффициенты ct .Неизвестные коэффициенты с, авторы находят путем решения системы из к уравнений типа (В 1) по заданным начальным членам рекуррентной последовательности (,у0, s^) k-ro порядка. Так как определитель этой системы является определителем Вандермонда, который не равен нулю, то система имеет однозначное решение относительно искомых коэффициентов с,-. Таким образом, каждому набору начальных членов О0, s^,) рекуррентной последовательности однозначно соответствуют коэффициенты сх,с2,.,ск над конечным полем GF(2k).

Лидл Р. и Нидеррайтер Г. [3] приводят также теорему, которая удвердает: если рекуррентной последовательности "So,^,^,^,. k-го порядка над простым полем GF{2) соответствует неприводимый характеристический многочлен Р(х) k-ой степени, то существует однозначно определенный элемент QeGF(2k), такой, что произвольный член sn рекуррентной последовательности может быть выражен через функцию-след как sn=T{0sn), п = 0,1,2,., (В2) где е — корень многочлена Р(х).

Однако, авторы доказывают лишь о существовании однозначно определенного элемента в и не приводят решения задачи нахождения такого элемента.

Таким образом, на основе выражений (В1) и (В2) могут быть построены новые алгоритмы декодирования рекуррентных последовательностей при известных коэффициентах с,,с2,.,с; для (В1) или в для (В2). Однако определение коэффициентов сх,с2,.,ск связано с решением системы из к линейно независимых уравнений по заданным начальным членам рекуррентной последовательности. При этом решение по правилам Крамера сводится к вычислению определителей, что при к>3 является довольно трудоемкой в вычислительном плане задачей. Поэтому, чтобы разработать эффективные алгоритмы обработки рекуррентных последовательностей на основе выражений (В1) и (В2), необходимо прежде решить математическую задачу по определению коэффициентов сх,с2,.,ск или элемента в . Причем, эффективность алгоритмов может быть существенно повышена, если определение коэффициентов с1,с2,.,ск или элемента в возможно будет производить не только по начальным членам последовательности но и по произвольному ^-элементному её участку

В этом случае можно будет применить мажоритарную процедуру декодирования рекуррентной последовательности.

Таким образом, учитывая огромное количество задач с применением рекуррентных последовательностей в телекоммуникациях, актуальной является проблема разработки новых алгоритмов обработки однородных линейных рекуррентных последовательностей на основе выражений (В1) и (В2). При этом ожидаемая высокая эффективность таких алгоритмов будет определяться высокой достоверностью и малым временем поиска ввиду применения мажоритарных методов декодирования по к-элементным участкам последовательности, а также простой вычислительной сложностью выражений (В1) и (В2).

Именно такая научная проблема ставится и решается в данной диссертационной работе на основе применения двойственного базиса конечного поля. Разработанные новые методы и алгоритмы позволяют более эффективно решать многие прикладные задачи в телекоммуникациях, связанные с формированием и обработкой линейных рекуррентных последовательностей. При этом повышение эффективности достигается благодаря применению мажоритарного принятия решения (по большинству), а также процедуры децимации принятой ЛРП.

Диссертационная работа состоит из двух частей. В первой части, содержащей первые четыре главы диссертации, рассматриваются теоретические аспекты двойственного базиса конечных полей и его применение для обработки ЛРП.

Вторая часть работы, состоящая из пяти последующих глав, посвящена применению полученных теоретических результатов в различных прикладных задачах телекоммуникаций.

В первой главе приведены определения и основные свойства линейных рекуррентных последовательностей. В качестве типовой ЛРП рассматривается последовательность максимальной длины - М-последовательность и ее свойства. Даны основные положения реализации устройств формирования линейных рекуррентных последовательностей на базе регистров сдвига с обратной связью.

Вторая глава является центральной теоретической главой первой части работы. В ней рассмотрены различные методы решения линейных модулярных рекуррентных уравнений (МРУ): 1) метод решения с помощью г-преобразований в конечном поле ОР(рА); 2) метод, основанный на использование двойственного базиса в конечном поле, при этом дается математическое решение задачи нахождения двойственного базиса по заданному примитивному (характеристическому) многочлену; 3) матричный метод решения МРУ над полем ОР(рА) по к произвольным линейно независимым членам рекуррентной последовательности.

Показано, что при определенных преобразованиях первый метод, как частный случай, приводится ко второму. Тем не менее, обосновывается вывод о предпочтении метода на основе двойственного базиса конечного поля.

Третья глава тесно связана со второй. В ней доказано, что метод на основе двойственного базиса, рассмотренный во второй главе, может также применяться для решения уравнений линейных рекуррентных последовательностей над полем GF( рк) с разложимым характеристическим многочленом, т.е. таким многочленом, который является произведением нескольких минимальных многочленов или, по-другому, полиномов деления круга в разложении двучлена -1) на неприводимые сомножители.

В качестве примера рассмотрены последовательности Гоулда и ЛРД-последовательности. Показано, что "прямые" и инверсные линейные рекуррентные последовательности могут быть представлены и, соответственно, решены на основе одного и того же рекуррентного уравнения с использованием двойственного базиса.

В четвертой главе изложены реализационные основы операций над элементами поля GF( рк ). Приводится реализация таких основных операций над элементами поля GF^') как умножение, деление, обращение элементов поля, нахождение функции следа от произвольного элемента поля. Приведена схема для определения двойственного базиса в поле GF(2*).

Пятая и шестая главы, первые две главы второй части, связаны между собой общим приложением. Обе они посвящены использованию результатов первой части, в частности двойственного базиса, в теории циклических кодов, комбинации которых представлены рекуррентными последовательностями. Рассмотрены эквидистантные циклические коды и дуальные коды БЧХ и Рида-Соломона. Показано, что мажоритарное декодирование, с учетом процедуры децимации, повышает корректирующие свойства циклических кодов как рекуррентных последовательностей.

Седьмая глава диссертации посвящена вопросам циклового фазирования и применению двойственного базиса для обработки фазирующей комбинации как рекуррентной последовательности. Благодаря применению двойственного базиса достигается повышение эффективности системы фазирования на базе М-последовательности. Отдельно рассмотрены вопросы фазирования скремблера и дескремблера в сетях ATM в процессе приема ATM- ячеек.

В восьмой главе рассмотрено применение двойственного базиса для обработки линейных рекуррентных последовательностей в специальных задачах, в частности при измерении дальности к объекту, а так же в системах передачи информации с «незакрепленной фазовой точкой».

Рассматривается возможность использования на приемной стороне двойственного базиса для оперативной оценки качества канала в процессе передачи данных по результатам мажоритарного декодирования комбинаций циклического кода как рекуррентных последовательностей.

В заключительной девятой главе показана возможность применения двойственного базиса для анализа числовых рядов, удовлетворяющих рекуррентному уравнению над полем действительных чисел, в частности, рядов обобщённых чисел Фибоначчи и чисел Люка [90].

В диссертации нашли отражение результаты многолетней работы автора по теоретическим исследованиям однородных линейных рекуррентных последовательностей и их применения для решения различных прикладных задач в телекоммуникациях с использованием двойственного базиса конечных полей.

Автор выражает благодарность своим аспирантам Д.С. Кукунину и С.С. Владимирову, которые, используя четвертую главу диссертации, разработали компьютерные варианты калькулятора Галуа. С помощью калькулятора были выполнены моделирование линейных рекуррентных последовательностей и их мажоритарная обработка с использованием двойственного базиса.

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Когновицкий, Олег Станиславович

Общие выводы по 9 главе.

1. Разработанная в дистанционной работе теория двойственного базиса применима для обработки также числовых однородных линейных рекуррентных (рекурсивных) последовательностей к-то порядка, члены которой удовлетворяют рекурсивному соотношению: ап = С\ап-\ +С2ап-2 +- + Скап-к = (~Р\)ап-\ +(гРг)ап-2+ — ']г^~Рк)ап-к^ П>к,

408 при условии, что характеристический многочлен Р(х) = р0хк + рххк~1 + .+рк\ р0 = 1, не имеет кратных корней.

В случае, если р0 ф 1, то постоянные коэффициенты с, должны быть равны с. = А

Ро

2. Числовые рекуррентные ряды легко синтезировать, задавая различные корни характеристического многочлена Р(х).

3. Могут быть построены периодические числовые рекурсивные последовательности с характеристическим многочленом, корни которого имеют комплексные числа.

4. Числовые рекуррентные последовательности могут найти применение для кодирования информации, для циклового фазирования и решения других задач.

5. Из теории двойственного базиса следует, что матрица, составленная из коэффициентов двойственного базиса, должна быть обратной по отношению к матрице корней в, характеристического многочлена Р(х).

Легко проверить, что для рекурсивной числовой последовательности второго

1 1 порядка матрица Y = будет обратной к матрице Z = ах а2

Д ßi т.е.

У-2-Е, где Е — единичная матрица.

Аналогично, для рекурсивной числовой последовательности третьего порядка матрицы 7 =

1 1 1 " а2 аъ ег «3 и Z = А ßi А е2 -У\ Vi Гг. являются обратными относительно друг друга.

заключение

В соответствии с поставленной целью в диссертации решена актуальная нучная проблема - разработаны теория, методы и алгоритмы решения ряда задач в телекоммуникациях на основе применения двойственного базиса и линейных рекуррентных последовательностей.

Получены следующие теоретические и практические результаты:

1. Разработан аналитический метод общего решения линейных модулярных рекуррентных уравнений в конечных полях на основе г-преобразований, а также на основе двойственного базиса. Выведены простые формулы для вычисления коэффициентов двойственного базиса в зависимости от вида характеристического многочлена анализируемой рекуррентной последовательности, а также формулы для определения значения произвольного члена рекуррентной последовательности.

2. Разработан аналитический метод общего решения на основе двойственного базиса составных рекуррентных последовательностей, в частности, последовательностей Гоулда и ЛРД-последовательностей, выявлен новый класс «зеркальных» последовательностей Гоулда и определены их свойства.

3. Предложен новый единый алгоритм обработки комбинаций циклического перестановочного кода по П. Нейману, т. е. «прямых» и инверсных рекуррентных последовательностей на основе двойственного базиса, что расширяет множество используемых комбинаций в два раза.

4. Разработаны основы реализации алгоритмов обработки линейных рекуррентных последовательностей над полем ОР(//), в том числе — формирования элементов двойственного базиса поля.

5. Разработаны на основе двойственного базиса алгоритмы декодирования комбинаций, как рекуррентных последовательностей, дуальных циклических кодов: эквидистантных, БЧХ и Рида-Соломона, обеспечивающие:

• исправление значительной доли ошибок, кратность которых превышает половину минимального кодового расстояния Хемминга вследствие применения децимаций и мажоритарного принципа декодирования;

• сокращение среднего времени декодирования комбинаций (и,т)-кода вследствие принятия решения «в целом» и обработке т-элементных участков комбинации;

• сложность реализации практически не зависимую от кратности исправляемых ошибок.

6. Доказаны теоремы, показывающие, что при определенных условиях эффективность обработки комбинаций циклических кодов, как рекуррентных последовательностей, с использованием двойственного базиса может быть повышена вследствие применения децимаций над принятой комбинацией.

7. Предложены новые более эффективные алгоритмы обработки рекуррентных последовательностей на основе двойственного базиса в задачах циклового фазирования (ЦФ), обеспечивающие уменьшение времени поиска и распознавания комбинаций ЦФ как рекуррентных последовательностей по сравнению с другими применяемыми методами рекуррентного поиска.

8. Предложены новые методы и алгоритмы решения ряда специальных задач в телекоммуникациях на основе применения двойственного базиса и линейных рекуррентных последовательностей. Эти методы и алгоритмы позволяют, в частности:

• уменьшить время измерения дальности до объекта с помощью длинных рекуррентных последовательностей, благодаря их обработке с использованием двойственного базиса;

• построить системы передачи данных с относительным изменением фазы рекуррентной последовательности, допускающие более низкие требования к стабильности задающего тактового генератора;

• упростить реализацию систем поиска и выделения длинных адресных рекуррентных последовательностей, особенно в беспроводных распределенных системах передачи данных;

• организовать оперативную оценку качества канала передачи данных в процессе передачи и обработки комбинаций как рекуррентных последовательностей.

9. Предложены новые, основанные на применении двойственного базиса, подходы к анализу числовых рекуррентных последовательностей (последовательностей чисел Фибоначчи, чисел Люка и др.) и принципы построения помехоустойчивых кодов над бесконечным полем целых чисел.

Конкретные примеры и результаты, подтверждающие эффективность использования двойственного базиса для обработки рекуррентных последовательностей в различных приложениях приведены в соответствующих главах диссертации.

В перспективе дальнейшие исследования по применению двойственного базиса должны быть направлены на решение следующих задач:

• Оценка эффективности декодирования комбинаций кода как рекуррентных последовательностей с использованием двойственного базиса в каналах с памятью;

• Анализ эффекта размножения ошибок при декодировании методом двойственного базиса по га-элементным участкам;

• Исследование эффективности обработки рекуррентных последовательностей методами двойственного базиса в сочетании с «мягкими» решениями;

• Исследования возможностей применения двойственного базиса в задачах криптографии.

Автор выражает благодарность своим аспирантам Кукунину Д.С. и Владимирову С. С., которые, используя четвертую главу диссертации, разработали компьютерный вариант калькулятора Галуа. С помощью калькулятора были выполнены моделирование линейных рекуррентных последовательностей и их мажоритарная обработка с использованием двойственного базиса.

Список литературы диссертационного исследования доктор технических наук Когновицкий, Олег Станиславович, 2011 год

1. Касами Т., Токура Н., Ивадари Е., Ирагаки Я. Теория кодирования. Пер. с япон. М.: Мир, 1978.-576 с.

2. Мак-Вильямс Ф.Дж., Споэн Н.Дж.А. Теория кодов, исправляющих ошибки. Пер. с англ. -М.: Связь, 1979.-744 с.

3. Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х томах. Пер. с англ. М.: Мир, 1988. - 818 с.

4. Питерсон Ч., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ. М.: Мир, 1976. -594 с.

5. Берлекэмп Э. Р. Алгебраическая теория кодирования. Пер. с англ. М.: Мир, 1971- 478 с.

6. Габидулин Э.М., Афанасьев В.Б. Кодирование в радиоэлектронике. — М.: Радио и связь, 1986.- 176 с.

7. Муттер В.М. Основы помехоустойчивой телепередачи информации. JL: Энергоатомиздат, Ленингр. отд., 1990. - 283 с.

8. Ван дер Варден Б.Л. Алгебра. Пер. с нем. / Под ред. Ю.И. Мерзлякова. М.: Наука, 1976. - 648 с.

9. Ленг С. Алгебра. Пер. с англ. / Под ред. А.И. Кострикина. М.: Мир, 1968. - 564 с.

10. Фараджев Р.Г. Линейные последовательностные машины.- М.: Сов. Радио, 1975. 248 с.

11. Маркушевич А.И. Возвратные последовательности. Популярные лекции по математике. Вып. 1. Изд. третье. М.: Наука, 1983. - 47 с.

12. Соломон Г. Алгебраическая теория кодирования. // В кн. «Теория связи». Пер. с англ. / Под ред. Б.Р. Левина. М.: Связь, 1972. - С. 234 - 287.

13. И.Лосев В.В., Бродская Е.Б., Коржик В.И. Поиск и декодирование сложных дискретных сигналов. — М.: Радио и связь, 1988. — 224 с.

14. Мишина А.П., Проскуряков И.В. Высшая алгебра. СМБ. М.: Наука, 1965.

15. Григорьев A.A. Некоторые мажоритарные алгоритмы определения фазы псевдослучайной последовательности // Изд. вузов СССР. 1979. - т. XXII, №-4. - с. 3341.

16. Канатова Л.В., Литвинов В.Л., Финк Л.М. Быстрое корреляционное декодирование р-ичных кодов максимальной длины // Проблемы передачи информации. 1986. — т. 22, вып. 2.-С. 98-103.

17. Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер. с англ. / Под ред. К.Ш. Зигангирова. М.: Мир, 1986. - 576 с.

18. Лосев В.В., Дворников В.Д. Определение фазы псевдослучайной последовательности по отрезку при помощи быстрых преобразований // Радиотехника и электроника. 1981. -Том 26, №8. - с.1666-1671.

19. Лосев В.В., Дворников В.Д. Распознавание адресных последовательностей при помощи быстрых преобразований // Радиотехника и электроника. 1983. - Том 28. № 8 - с. 15401547.

20. Лосев В.В. Обнаружение последовательностей Голда при помощи быстрых преобразований // Радиотехника и электроника. 1981. - Т. 26. № 8. — с. 1660-1665.

21. Лосев B.B. Определение фазы псевдослучайной последовательности // Изв. вузов СССР. Радиоэлектроника. 1980. - Т. 23. № 12 - с. 81-82.

22. Сарвате Д.В., Персли М.Б. Взаимно-корреляционные свойства псевдослучайных и родственных последовательностей // ТИИЭР. 1980. - Т. 68. № 5. - с. 59-90.

23. Золотарев В.В. Теория и алгоритмы многопорогового декодирования. — М.: Радио и связь, 2006. 266 с.

24. Месси Дж. Пороговое декодирование. Пер. с англ. / Под ред. Э.Л. Блоха. М.: Мир, 1966.-207 с.

25. Цирлер Н. Линейные возвратные последовательности // Кибернетический сборник. 1963. Вып. 6. Zierler N. Linear vecurring sequences,// «J. Soc. Ind. Appl. Math.»,v. 7, 1959, №1, С. 31-48.

26. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Пер. с англ. М.: Радио и связь, 1987. — 391 с.

27. Варакин Л.Е. Системы связи с шумоподобными сигналами. — М.: Радио и связь, 1985. -384 с.

28. Тепляков И.М., Рощин Б.В., Фомин А.И., Вейценг В.А. Радиосистемы передачи информации. М.: Радио и связь, 1982. —264 с.

29. Когновицкий О.С. Алгебраический метод нахождения двойственного базиса в поле Галуа GF(2K) и его практическое применение. // Теория передачи информации по каналам связи: Сборник научных трудов учебных инст. связи ЛЭИС. - Л., 1982. С. 10 -18.

30. Диксон Р.К. Широкополосные системы. / Пер. с англ. Л.Ф. Жигулина. М.: Связь, 1979. - 302 с.

31. Журавлев В.И. Поиск и синхронизация в широкополосных системах. М.: Радио и связь, 1986.-240 с.

32. Шумоподобные сигналы в системах передачи информации / Под ред. В.Б. Пестрякова. -М.: Советское радио, 1973. 423 с.

33. Алексеев А.И. и др. Теория и применение псевдослучайных сигналов. М.: Наука, 1969. -365 с.

34. Петрович Н.Т., Размахнин М.К. Системы связи с шумоподобными сигналами. — М.: Советское радио, 1969. 232 с.

35. Mac Williams F.J. and Sloane N.J. Pseudo random sequences and arrays, Proc. IEEE, 64, (1978), 1715-1729). ( Перевод в журнале ТИИЭР. 1976. T. 1. №12. - с. 80-95.

36. Смирнов Н.И. Применение М-последовательностей в асинхронных радиотехнических системах. // Электросвязь. 1979. №10. — с. 33-42.

37. Гантмахер Ф.Р. Теория матриц. — М.: Наука, 1967. — 575 с.

38. Элспас Б. Теория автономных линейных последовательных сетей // Кибернетический сборник-М.: ИЛ, 1963.-с. 91-128.

39. У орд Р. Различение псевдошумовых сигналов методом последовательной оценки // Зарубежная радиоэлектроника. 1966. №8.

40. Деч Г. Руководство к практическому применению преобразования Лапласа и Z-преобразования. Пер. с нем. М.: Наука, 1971.

41. Аракелов В. А., Варшамов P.P. К исследованию алгебраической структуры периодических рекуррентных последовательностей.// Известия академии наук

42. Армянской ССР.Математика./ Ереванский гос. ун-т Ереван: VI, № 5, 1971. - С. 379 -385.

43. Блох Э.Л., Лошинский Л.И., Турин В.Я. Основы линейной алгебры и некоторые ее приложения. -М.: Высшая школа, 1971.

44. Маттсон Х.Ф., Соломон Г. Новая трактовка кодов Боуза-Чоудхури // Теория кодирования: Сборник статей. Пер. с англ. / Под ред. Э. Л. Блоха. М.: Мир, 1964. - С. 7 -29.

45. Лезин Ю.С. Оптимальные фильтры и накопители импульсных сигналов. — М.: Советское радио, 1964.

46. Деев В.В. Методы модуляции и кодирования в современных системах связи. — СПб.: Наука, 2007. 267 с.

47. Мэзон В., Циммерман Г. Электронные цепи и системы. -М.: ИЛ, 1963.

48. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1964.

49. Когновицкий О. С. Основы циклических кодов: Учебное пособие / ЛЭИС. — Л., 1990.

50. Kilgus Charles С. Pseudo-noise code acquisition using majority logic decoding. IEEE Int. Conf. Commun. Seattle. Wash., 1973, New York. ( Применение PN-кодов с мажоритарным декодированием // Экспресс-информация. Серия ПИ. 1974. №11.)

51. Новиков И.А., Номокопов В.Н., Шебанов A.A., Яковлев Д.О. К вопросу о мажоритарном декодировании m-последовательностей // Серия общетехническая. 1976. Вып. 5. — с. 5055.

52. Golomb S.W. Sequences with randomness properties. Final Riport, Baltimore, Md., 1955.

53. Golomb S.W. Structural properties of PN sequences. Technical Report, Jet Propulsion Lab., Califjrnia Institute of Technology, Cal., 1958.

54. Arazi B. Decimation of m-sequences leading to any desired phase shift. Electron. Left. 13, 1977.

55. Питерсон У. Коды, исправляющие ошибки. Пер. с англ. М.: Мир, 1964. - 338 с.

56. Когновицкий О.С. Об одном алгоритме мажоритарного декодирования кодов максимальной длины // Девятая всесоюзная конференция по тезисам кодирования и передачи информации, тезисы докладов. Часть 2. Одесса. 1988. с. 195-197.

57. Сагалович Ю.Л. Последовательности максимальной длины как коды состояний автомата. Проблемы передачи информации.: т. 13, вып. 4., 1976. С. 70 - 73.

58. Когновицкий О.С., Сюрин В.Н., Ассанович Б.А. Метод вычисления логарифма в конечном поле GF(2m) // Девятая всесоюзная конференция по теории кодирования и передачи информации: Тезисы докладов. Часть 1. Одесса. 1988. с. 100-102.

59. Когновицкий О.С., Буданов A.B., Брызгана Г.П. Кодирующее устройство кода Рида-Соломона: Авторское свидетельство СССР №1716609, Н03 М. Бюллетень №8, 29.02.92.

60. Шахнович И. Современные технологии беспроводной связи. -М.: Техносфера, 2004.

61. Бабков В.Ю., Никитин А.Н., Осенний К.Н., Сивере М.А. Системы мобильной связи с кодовым разделением каналов. СПб.: ТРИАДА, 2003.

62. Присяжнюк С.П. Обработка и защита информации в автоматизированных системах лучевой энергетики: Учебное пособие / Балт. гос. техн. ун-т. СПб., 2005. - 147 с.415

63. ITU-T Recommendation 1.432.1. B-ISDN User-Networks Interface: Physikal Layer Shecification, 1999.

64. Когновицкий O.C., Нгуен Тиен Бан. Методы синхронизации дескремблера по распределенным образцам в сетях АТМ // Труды учебных заведений связи / СПбГУТ. 2003. №169.

65. Когновицкий О.С., Нгуен Тиен Бан. Модели и методы расчета характеристик процессов скремблирования ячеек в сетях АТМ // Труды учебных заведений связи СПбГУТ. 2003. №169.

66. Когновицкий О.С. Алгоритмы обработки рекуррентных псевдослучайных последовательностей в задачах передачи данных // Связисты СПбГУТ и телекоммуникации XXI века: тр. / СПбГУТ. 2000.

67. Лагутенко О.И. Современные модемы. -М.: Эко-Трендз, 2002.

68. Григорьев В.А., Лагутенко О.И., Распаев Ю.А. Сети и системы радиодоступа. М.: Эко-Трендз, 2005.

69. Вишневский В.М., Ляхов А.И., Портной С.Л., Шахнович И.В. Широкополосные беспроводные сети передачи информации. М.: Техносфера, 2005.

70. Kim S.С. and Lee В.G. Synchronization of shift register generators in distributed Sample scramlers // IEEE Transactions on Communications, 1994. Vol. 42, №3.

71. Дж. Спилкер. Цифровая спутниковая связь. Пер. с англ. / Под ред. В. В. Маркова. М.: Связь, 1979.

72. Когновицкий О.С., Кукунин Д.С. Метод декодирования эквидистантных кодов с использованием двойственного базиса поля Галуа // Труды учебных заведений связи / СПбГУТ. 2006. №174.

73. Когновицкий О.С. Циклические коды БЧХЭ как рекурсивные последовательности // Труды учебных заведений связи / СПбГУТ. 2006. №174.

74. Когновицкий О.С., Кукунин Д.С. Методика оценки качества канала при передаче рекурсивных последовательностей // Труды учебных заведений связи / СПбГУТ. 2007.№178.

75. Когновицкий О.С., Свердлов Л.М. Мажоритарное декодирование М-последовательностей с использованием децимаций // 49-я НТК: Тез. докл. / СПбГУТ. 1996

76. Когновицкий О.С. Циклические коды Рида-Соломона как рекурсивные последовательности // Труды юбилейной Х-й Санкт-Петербургской международной конференции "Региональная информатика ( РИ-2006 )". СПбИСУ. 2007.

77. Когновицкий О.С., Сюрин В.Н., Михеев И.С. Устройство для передачи и приема дискретной информации: Авторское свидетельство №642867, Н04 17/00, Н04 3/00. Бюллетень изобретений №2, 1979.

78. Когновицкий О.С., Сюрин В.Н. Метод передачи данных, кодируемых изменением фазы псевдослучайной последовательности. "Системы и аппаратура передачи данных" // Сборник научных трудов ЦНИИС. М.,1981.

79. АС. 886295 (СССР). Устройство для передачи и приема дискретной информации / О.С. Когновицкий, В.Н. Сюрин, А.Н. Глухов. Опубликовано в Б.И. 1981. №44.

80. A.C. 886296 (СССР). Система для передачи и приема дискретной информации / О.С.Когновицкий, В.Н. Сюрин. — Опубликовоно в Б.И. 1981. №44.

81. A.C. 1149428 (СССР). Устройство для приема дискретных сигналов / В.Н. Сюрин, О.С, Когновицкий, Ю.Б. Окунев. Опубликовано в Б.И. 1985. №13.

82. A.C. 429543 (СССР). Устройство для автоматического измерения характеристик дискретного канала. / О.С. Когновицкий, В.В. Гнилицкий. Опубликовано в Б.И. 1974. №19.

83. A.C. 535743 (СССР). Устройство для автоматического измерения характеристик дискретного канала. /О.С. Когновицкий, В.В. Гнилицкий. — Опубликовано в Б.И., 1976.№42.

84. A.C. 660276 (СССР). Устройство для автоматического измерения характеристик дискретного канала. / О.С.Когновицкий, A.B. Чулкин. — Опубликовано в Б.И., 1979. №16.

85. Когновицкий О.С., Гнилицкий В.В., Чулкин A.B. Методика исследования каналов передачи данных со сбоями синхронизации. "Системы и аппаратура передачи данных": Сборник научных трудов / ЦНИИС. М., 1981.

86. A.C. 1504807 (СССР). Устройство для измерения характеристик дискретного канала связи / О.С. Когновицкий, Г.М. Марголин, A.B. Чулкин. — Опубликовано в Б.И., 1989. №32.

87. Блох Э.Л. Модели источника ошибок в каналах передачи цифровой информации / Э.Л.Блох, О.В. Попов, В.Я. Турин. -М.: Связь, 1971.

88. Стахов А., Слученкова А., Щербаков И. Код да Винчи и ряды Фибоначчи. СПб.: Питер, 2006.

89. Воробьев H.H. Числа Фибоначчи. Издание пятое. М.: Наука, 1984.

90. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Пер. с англ. В.Б. Афанасьева. М.: Техносфера, 2006. - 319 с.

91. Кукунин Д.С., Когновицкий О.С. Адаптация системы передачи к состоянию канала // 60-я НТК: мат-лы / СПбГУТ. СПб, 2008. С.28-29.

92. Кукунин Д.С., Когновицкий О.С. Методика оценки качества канала в процессе передачи данных // Научно-технические ведомости СПбГПУ. 5(65), СПб, 2008. С. 86 92.

93. Свидетельство о государственной регистрации программы для ЭВМ №2009612476. Мультиоперационный калькулятор Галуа, версия 1.1./ Кукунин Д.С., Когновицкий О.С. Зарегистрировано 18.05.2009 г.

94. Когновицкий О.С. Циклические коды Рида-Соломона как рекурсивные последовательности и их декодирование с использованием двойственного базиса // Научно-технические ведомости СПбГПУ. 4(82), СПб, 2009. С. 47 59.

95. Когновицкий О.С. Двойственный базис и его применение в телекоммуникациях. -Издательство «Линк», Санкт-Петербург, 2009, 411с.

96. Когновицкий О.С. Анализ прямых и инверсных последовательностей. // Научно-технические ведомости СПбГПУ. 3(101), СПб, 2010. С. 15 20.

97. Когновицкий О.С. Анализ рекуррентных последовательностей чисел Фибоначчи с использованием двойственного базиса. Издательство «Линк», Санкт-Петербург, 2010, 60с.

98. Нечаев В.И. Рекуррентные последовательности.// Учен. зап. Московск. пед. инст. т. 375, 1971. С. 103- 123.

99. Нечаев A.A. Линейные рекуррентные последовательности над коммутативными кольцами.// Дискретная математика. 3 (4), 1991. С. 105 127.

100. Радченко А.Н., Филиппов В.И. Сдвигающие регистры с логической обратной связью и их использование в качестве счетных и кодирующих устройств. — Автоматика и телемеханика, т. 20, № 11, 1959. С. 1507 1514.

101. Боуз Р.К., Рой-Чоудхури Д.К. Об одном классе двоичных групповых кодов с исправлением ошибок.// Кибернетический сборник —М., ИЛ, 1961, вып. 2. С. 83 - 94.

102. Галлагер Р. Теория информации и надёжная связь. М.:Советское радио, 1974. - 719 с.

103. Горинстейн Д., Питерсон В., Цирлер Н. Квазисовершенность кодов Боуза Чоудхури с исправлением двух ошибок.// Кибернетический сборник - М., ИЛ, 1963, вып. 6. - С. 20 -24.

104. Рид И.С. Класс кодов с исправлением нескольких ошибок и схема декодирования. // Кибернетический сборник М., ИЛ, 1960, вып. 1. - С. 189 - 205.

105. Варшамов P.P., Остиану В.М. Применение теории конечных полей к теории корректирующих кодов и синтезу надёжных релейных структур. В кн.: Теория конечных и вероятностных автоматов. М.: Наука, 1965. С. 376 - 378.

106. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. М.: Связь, 1968.-251 с.

107. Стародубцев В.Г., Павлов O.A. Помехоустойчивые коды в телекоммуникационных и информационных системах. Выпуск 1. Конечные поля Галуа: элементы теории и практики: учебное пособие / BKA им. А.Ф. Можайского. СПб., 2003. - 255 с.

108. Меггит Дж. Коды, исправляющие ошибки, и их применение в системах передачи информации // Теория кодирования: Сборник статей. Пер. с англ. / Под ред. Э. Л. Блоха. М.: Мир, 1964. - С. 225 - 256.

109. Нейман П. Заметки о циклически перестановочных кодах, исправляющих ошибки.// Теория кодирования: Сборник статей. Пер. с англ. / Под ред. Э. Л. Блоха. — М.: Мир, 1964.-С. 65-82.

110. Кукунин Д.С. Модель системы с адаптивным выбором кода.// Научно-технические ведомости СПбГПУ. 5(65), СПб, 2008. С. 81 86.