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

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

Специальность: 05.12.13 - Системы, сети и устройства телекоммуникаций

Автореферат диссертации на соискание ученой степени доктора технических наук

1 9 МАЙ 2011

Санкт-Петербург 2011

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М. А. Бонч-Бруевича.

Официальные оппоненты: доктор технических наук, профессор

Эрнст Мухамедович Габидулип

доктор технических наук, профессор Сергей Прокофьевич Присяжнюк

доктор технических наук, профессор Владимир Викторович Деев

Ведущая организация: Военная академия связи им. С. М. Буденного

Защита состоится « » июня 2011 г. в /Учас.на заседании диссертационного совета Д 219.004.02 при Санкт-Петербургском государственном университете телекоммуникаций им. проф. М. А. Бонч-Бруевича по адресу: 191186 Санкт-Петербург, наб. р. Мойки, 61, ауд. 205.

чс-

С диссертацией можно ознакомиться в библиотеке университета.

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

Автореферат разослан « ¿*У» 20111

Ученый секретарь диссертационного совета кандидат технических наук, доцент

X. Харитонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Значительное число работ как зарубежных так и отечественных авторов посвящено апализу и синтезу ЛРП максимального периода, называемых также М-последователыюстямн, псевдослучайными (ПСП) или шумоподобными (ШПС) последовательностями. Наибольшую известность получили работы в этом направлении Н.Цирлера, Б. Элспаса, Д. Сарвате, С. Голомба и др. Из отечественных авторов, внесших существенный вклад в развитие линейных рекуррентных последовательностей, следует назвать P.P. Варшамова, А.И. Маркушевича, A.A. Нечаева, В.И. Нечаева, Ю.Л. Сагаловича.

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

Большой обобщающий материал по теории ЛРП содержится в двухтомнике Р. Лидла и Г. Нидеррайтера. Конечные поля. - М.: 198В.

Одной из важных задач является выбор эффективного способа обработки линейных рекуррентных последовательностей в различных приложениях. При этом критерий эффективности определяется конкретными требованиями к системо^^

Как следует из многих литературных источников, практическое применение находят, в основном, три способа обработки: корреляционная обработка, обработка на основе рекуррентного соотношения и алгебраическая обработка иа основе теории конечных полей. Наиболее эффективной и простой реализацией корреляционного способа является применение согласованных фильтров, однако, при декодировании множества комбинации этот способ требует значительных материальных затрат при апаратной реализации, так как необходим согласованный фильтр на каждую отдельную кодовую комбинацию. Другим вариантом решения такой задачи для эквидистантных кодов является метод максимального правдоподобия, в основе которого лежит умножение принятой комбинации на циркулянтную квадратную матрицу А размером NxN, строками которой будут все циклические сдвиги М-последовательности длиной N. Однако при больших длинах комбинации и этот метод требует также значительных материальных затрат при аппаратной реализации либо больших задержек при программной реализации.

Для обработки рекуррентных последовательностей, в том числе и произвольной структуры, часто применяют методы, основанные на свойстве рекуррентности. К ним можно отнести рекуррентный опозпаватель по методу Р. Уорда и метод безошибочного «зачетного» участка. Такие способы просты в реализации, но решают очень узкую задачу, а именно, лишь опознавание рекуррентной последовательности, т.е. они не могут идентифицировать разные рекуррентные последовательности по начальной фазе.

Алгебраической структуре периодических рекуррентных последовательностей посвящены исследования P.P. Варшамова и В.А. Аракелова, в работах которых предложен метод определения специальных коэффициентов, позволяющих аналитически находить произвольный п-й элемент рекуррентной последовательности по начальным элементам данной последовательности. Вычисление специальных коэффициентов проводится на основе решения диофантова уравнения для заданного значения п. В связи с тем, что решать диофантовы уравнения необходимо для каждого из п, предложенный метод имеет большую вычислительную сложность. Кроме того, применение этого метода ограничивается анализом структуры лишь «чистой» рекуррентной последовательности и невозможностью его применения для декодирования (обработки) рекуррентной последовательности, содержащей ошибки. Поэтому он не нашел практического применения.

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

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

Исследования в этом направлении были проведены Р.Г. Фараджевым, который применил для решения указанной выше задачи дискретное преобразование Лапласа [Ор -преобразование). Однако разработанный им метод, как и указанный выше метод на основе диофантовых уравнений, находит и-й член линейной рекуррентной последовательности также только относительно исходных начальных членов рекуррентной последовательности над простым полем с характеристикой р. Это, следовательно, не позволяет применить предложенный метод в тех случаях, когда должна быть решена обратная задача -определение начальных элементов последовательности (её фазы) по некоторым произвольным принимаемым элементам последовательности.

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

Таким образом, объектом исследований являются линейные рекуррентныые последовательности (ЛРП), широко применяемые в настоящее время в телекоммуникациях, в навигации и в телеметрии: М-последовательности, последовательности Гоулда, ЛРД-последовательности, а также комбинации циклических кодов как рекуррентные последовательности.

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

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

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

Для достижения этой цели в диссертации поставлены следующие задачи:

- разработать аналитические методы общего решения однородных ЛРП;

- разработать алгоритмы обработки ЛРП на основе двойственного базиса;

- исследовать влияние децимаций на достоверность мажоритарной обработки ЛРП с использованием двойственного базиса;

- разработать основы реализации алгоритмов обработки ЛРП с учетом использования двойственного базиса;

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

- провести путем имитационного моделирования экспериментальное исследование влияния на достоверность мажоритарной обработки ЛРП с использованием двойственного базиса;

- провести сравнение разработанных алгоритмов обработки ЛРП с другими известными алгоритмами.

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

Для подтверждения полученных теоретических результатов использовались компьютерное моделирование, электронный инструментарий - калькулятор Галуа, методы математической статистики и теории вероятностей:

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

В процессе проведения исследований получены новые научные результаты:

Теоретического характера

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

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

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

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

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

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

Пприкладного характера

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

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

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

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

• при измерении дальности до объекта;

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

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

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

Практическая ценность диссертационной работы определяется тем, что применение двойственного базиса для обработки однородных ЛРП позволит:

- повысил, достоверность принятия решения при обработке принятых по каналу с ошибками однородных рекуррентных последовательностей;

- уменьшил, время поиска ЛРП, используемых в качестве комбинаций циклового фазирования;

- повысить оперативность в оценке качества каналов передачи данных;

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

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

Реализация и внедрение результатов исследований

На основе разработанных в диссертации мажоритарных алгоритмов обработки рекуррентных последовательностей в СПбГУТ им. проф. М.А. Бонч-Бруевича выполнены фундаментальные НИР по разработке эффективных помехоустойчивых циклических кодов с использованием двойственного базиса (отчеты с номерами государственной регистрации № 01200964865,2009 и № 01970006723,2010).

Разработан «Мультипрограммный калькулятор Галуа, версия 1.1», свидетельство № 2009612476, зарегистрировано в Реестре программ для ЭВМ 18.05.2009.

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

научно-производственное предприятие «ИСТА-Системс» - в опытно-конструкторской разработке автоматизированной информационной системы видеонаблюдения Санкт-Петербурга, созданной в рамках реализации программы «Автоматизированная информационная система обеспечения безопасности жизнедеятельности»;

- иаучно-производственное предприятие «Импульс» - при создании аппаратуры дистанционного управления и контроля для системы телеметрических измерений, шифр разработки «4202-АУКТ»;

- Санкт-Петербургский институт информатики и автоматизации РАН (СПИИРАН)-в НИР «Разработка методов и алгоритмов моделирования жизненных циклов мобильных информационных технологий», выполняемой в рамках программы фундаментальных научных исследований отделения нанотехнологий и информационных технологий Российской академии наук (Проект 0-2.3);

- ФГУП ЦНИИ «Электроприбор» - в планируемой ОКР (шифр «Кудесник») по созданию аппаратуры связи специального назначения;

- СПбГУТ им. проф. МЛ. Бонч-Бруевича - в учебном процессе на кафедре «Обработки и передачи дискретных сообщений» при преподавании дисциплины «Передача дискретных сообщений», при подготовке аспирантов, магистров, а также в дипломном проектировании.

Соответствующие акты об использовании результатов работы прилагаются.

Апробация. Основные положения диссертационной работы были представлены и обсуждались на:

• 4-й Всесоюзной школе-семинаре по вычислительным сетям «Помехоустойчивое кодирование и сжатие данных». Москва-Ташкент, 1979;

• 9-й Всесоюзной конференции по теории кодирования и передачи информации. Одесса, 1988;

• У11 научно-технической конференции НТОРЭС им. A.C. Попова «Оптические, сотовые и спутниковые сети и системы связи». Санкт-Петербург (г. Пушкин), 1996;

• X Санкт-Петербургской международной конференции «Региональная информатика — 2006». Санкт-Петербург, 2006;

• Международной научно-технической конференции «Актуальные проблемы анализа и построения информационных систем и процессов». Таганрог, 2010;

• 1 Международном конгрессе «Современные аспекты математики гармонии и ее применение в экономике, естествознании, технологии, социуме и образовании». Одесса, 2010;

а также на семинарах и научно-технических конференциях профессорско-преподавательского состава СПб ГУТ им. проф. М.А. Бонч-Бруевича.

Публикации. Основные результаты дисссртационпой работы опубликованы в 53 работах, в числе которых 18 научных статей, из них 13 в периодических изданиях, находящихся в перечне ВАК или находившихся в этом перечпе на момент опубликования, 10 авторских свидетельствах СССР и два патента РФ на изобретения, одпо свидетельств о государственной регистрации программы для ЭВМ, одна монография, одна брошюра и два учебных пособия.

Структура и объем работы. Диссертационная работа состоит из введения, 9 глав в двух частях, заключения, списка литературы и приложения. Общий объем диссертации составляют 427 страниц, включая 106 рисунков и 36 таблиц.

Основные положения работы, выносимые на защиту:

1. Разработанный на основе г-преобразования аналитический метод определения произвольного п-го члена однородной рекуррентной последовательности {s} к-то порядка по заданным начальным элементам (so, ,—А -i) или исходному элементу поля с0 = Вi(0).

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

3. Матричный метод решения однородных ЛРП над полем GF^) по к произвольным линейно независимым элементам рекуррентной последовательности.

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

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

6. Основы реализации алгоритмов обработки линейных рекуррентных последовательностей над полем GF(рк), в том числе:

- схема формирования элементов двойственного базиса поля;

- аналитический метод реализации логарифмирования и ашилогарифмирования над элементами поля GF(A

- реализация процедуры нахождения функции следа;

- алгоритм упрощенной реализации умножения на двоичную матрицу.

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

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

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

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

8. Новые алгоритмы обработки рекуррентных последовательностей на основе двойствешюго базиса в задачах циклового фазирования в системах передачи данных, в которых в качестве фазирующих комбинаций могут использоваться: М-последователыюсти, последовательности Гоулда, ЛРД-последователыюсти.

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

• при измерении дальности до объекта;

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Первая глава посвящена общему анализу линейных рекуррентных последовательностей {$} к-то порядка над конечным полем GF(p), удовлетворяющая однородному рекуррентному уравнению

■5Vrt=PlS/Hк-\+ P2Sn+t-2+- ■ -+PtS„ , п = 0, 1, 2, ..., (1)

которому, в свою очередь, соответствует нормированный характеристический многочлен

P(x)=jk+pixk~l +Р2^~2 +... +pt-,x+pi-, р, е GFO). (2)

Характеристический многочлен (2) представляет собой определитель квадратной матрицы к-то порядка [xE-F], где Е - единичная квадратная матрица, а F — сопровождающая квадратная матрица, соответствующая многочлену Р(х).

Корни многочлена Р(х) сь £2, ■•• , г*, называемые характеристическими числами, являются решением векового уравнения det[xE-f] = 0. Как видно из векового уравнения, одним из корней многочлена Р(х) является сама матрица F, т.е. P{F) = 0.

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

Другое основополагающее свойство ЛРП, используемое в диссертационной работе, формулируется следующим образом: Если корни ej, £?, •■■ , et характеристического многочлена Р(х), соответствующего однородной ЛРП {j} k-го порядка, различны, то произвольный член s„ этой последовательности над полем GF(p) будет равен

s„ = п = 0,1,2,..., (3)

1-1

где С], сг, .... а —элементы расширенного поля GF(pk), которые однозначно определяются начальными членами so, s¡,..., si¡-¡ рекуррентной последовательности {s}.

Одной из главных научных проблем диссертации явилось аналитическое решение линейной рекуррентной последовательности, состоящее в определении коэффициентов сь С2, ..., c¿, позволяющих, в соответствии с (3), находить произвольный член s„ ЛРП.

Как следует из ряда опубликованных работ, коэффициенты с\, съ ..., c¿ определялись путем прямого решения системы линейных уравнений (3) по заданным начальным членам jo, si,—, ¿'¿--i рекуррентной последовательности {í}. Однако, решение системы уравпений при к>3 вызывает определенные затруднения реализационного плана. Поэтому многие исследователи пытались решить эту задачу так, чтобы коэффициенты c¡, съ..., qможно было находить из простых выражений, легко реализуемых как программно, так и алпаратно. Именно такая задача решается в первой части диссертационной работы. Решение этой теоретической задачи в диссертации получено для однородных лилейных рекуррентных последовательностей, в частности, для последовательностей максимальной длины (М-последовагельностей), последовательностей Гоулда, ЛРД-последовательностей, а также кодовых комбинаций циклических кодов как рекуррентных последовательностей (дуальных циклических кодов).

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

Вторая глава диссертации посвящена аналитическому решению линейных возвратных модулярных уравнений над конечным полем (по определеншо Р.Г. Фараджева). Разработаны три метода аналитического решения однородных модулярных рекуррентных уравнений (МРУ).

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

Теорема 2.1. Пусть So, íi, s¡, ... однородная линейная рекуррентная последовательность k-го порядка над полем GF(pk) и Р(х) = ро ¿ - p¡ я*"' - ... pt-\ х-рь

4-1

pie GF(p), - ее нормированный характеристический многочлен. Если корни s,ep.....SP

многочлена Р(х) все различны, то s„ равен функции-спед: s„ = Т[В\(п)].

При этом

в,(п) = -/T<"+,>¿ímA ; GF(pk), (4)

i-l

где sa, íi.....Jt-i - начальные члены рекуррентной последовательности;

ß = £ ' - корень многочлена <Э(х), двойственного по отношению к Р(х);

м, = Рл ■ < = 1,2.....(5)

Как видно из формулы (4), начальная фаза рекуррентной последовательности {у} может быть задана исходным элементом поля 0¥(р), который будет равен с0 = Л[(0). Именно этому элементу со, записанному в ячейки модулярного регистра, соответствует начальный элемент последовательности ъ, = Т(с0) = Г(В|(0)).

Таким образом, в диссертации на основе 2-преобразования разработан аналитический метод определения значения произвольного и-го члена однородной рекуррентной последовательности {¿} к-го порядка по заданным начальным ее элементам (яо ... ^ы).

Аналогичная задача была решена Р.Г. Фараджевым на основе применения /^-преобразования (дискретного преобразовашм Лапласа) над полем вТ(р).

Однако, часто возникает более общая задача, когда по произвольному к-элементному участку принимаемой рекуррентной последовательности необходимо определить ее начальные элементы или ее начальную фазу со. Такая задача стоит при обеспечении циклового фазирования с помощью М-последовательностей, при декодировании циклических кодов максимальной длины и в некоторых других случаях. Похожие задачи стоят при определении расстояния (в числе элементов) от выделенного ¿-элементного участка {$„, ¿„+1, ...А+ы) М-последовательносги до ее начала. Задачи такого типа впрямую не решает ни метод на основе г-преобразования, разработанный в данной главе диссертации, ни метод Р.Г. Фараджева.

Второй метод решения однородных линейных МРУ основан на применении двойственного базиса конечного поля. Применяя математический аппарат высшей алгебры, в частности, полей Галуа, в диссертации доказано, что произвольный элемент л„ линейной рекуррентной последовательности {4} с характеристическим многочленом Р(х) к-й степени определяется функцией-след

= (6)

м

где Е - корень характеристического многочлена Р(х);

с - коэффициент, который находится из выражения

к

п - расстояние ¿-элементного участка (5,ац, ...а+ы) от начала последовательности:

М = (*о, .VI, 53, , ) = №), Дсе), Дсе2), Псе3),..., Цсе"'-1)). (8)

е-2

В выражении (7) коэффициенты со, представляют собой двойственный базис поля ОГ(рк), который определяется по следующей теореме, доказанной в диссертации.

Теорема 2.2. Если степенной базис (у1,у2,...,у1) поля О-Гф4)равен (е"'), где е - корень примитивного полинома Р(х) степени к, то двойственный (взаимный) базис со1,со2.....о>1[ определяется выражением:

ет( = е"а. ; I = 2,..., (9)

где а'В"*Р'(е) ; ^ (10)

р„, - коэффициенты характеристического полинома.

Несколько другие формулы для коэффициентов а, как двойственного базиса элементов поля GF(pk) относительно левого степенного базиса получены американским математиком, профессором Колумбийского университета С. Летом. Так, он показал, что

двойственным базисом по отношению к левому степенному базису (1,£ ,е2,...,е ') будут

v v v следующие элементы поля: ——, —■—,..., ——.

Р'(е) Р'(с) Р\е)

При этом коэффициенты v. е GF(рк) находятся из частного от деления: Pix) »-1

. (11)

Вместе с тем, следует заметил., что формулы С. Лента представляют собой выражения для двойственного базиса только для одного частного случая, а именно только

относительно левого степенного базиса (1,е '). Тогда как в диссертационной

работе, в отличие от результата С. Лента, получены и строго математически доказаны общие выражения для двойственного базиса поля GF(p*) относительно произвольного

я л + 1 л+i-l. -

степенного базиса (е ,е ,...,£ ), в том числе и для п = 0.

Таким образом, в диссертации решена фундаментальная задача - определение, на основе двойственного базиса, начальной фазы рекуррентной последовательности {j} (в виде её начальных элементов (so, si, —. if-i), GF(p) или в виде элемента расширенного поля ceGF(pk)) по произвольному безошибочному ¿-элементному участку (j„, Sn+U — , -Уп+ifc-l) последовательности. В дальнейших главах диссертации это свойство использовано для мажоритарного декодирования циклических кодов как рекуррентных последовательностей.

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

последовательности {s}. При этом, для решения поставленной задачи выбираются к линейно независимых элементов последовательности {5}, а именно s , s.^, s^, ..., s^, из

которых, с учетом (6), составляется система уравнений:

s,=T(e"*i) = T(cel), (12)

где c = sm определяет начальную фазу последовательности {.г}, а j принимает значения i), ¿2,..., 4. Известными величинами в системе уравнений (12) являются значения индексов ii, h, —А относительно «закрепленной» точки и значения самих линейно независимых элементов s.^, s ,..., s е GF(p) последовательности {s}. В результате решения системы

уравнений (12) необходимо определить элемент поля е" =aa + aß + a2c2 +...+at_^t~\ где a:eGF(p).

В диссертации показано, что система уравнений (12) может быть преобразована к виду sj = \a\-F' во =Дао, а,, аг,... аы); GF(p) (13)

где F - сопровождающая матрица, во - младший вектор-столбец матрицы в, равной поэлементной сумме по модулю р матриц возведения элемента поля GF(p) в степени /У, а именно матриц: единичной Е - ддяу = 0; Х-для у = 1; У-для у = 2;..., 2-для j = (k-\), т.е.

в - [£ + АГ+ У+ ... + 2]; (14)

/¡{ая, в|, аг, ... ctk-1) - функционал, представляющий собой сумму по mod р определенных элементов вектора |я| = [ао, au аг,..., 04. i] с множителями - вычетами по mod р.

Полученная система линейно независимых уравнений (13) окончательно решается относительно элементов ао, ai, аг, ..., ом, что и дает векторное представление элемента

с= с", определяющего начальную фазу последовательности {s}.

В результате сравнения разработанных аналитических методов решения линейных МРУ сделан вывод, что первый вариант на основе 2-преобразований позволяет по известному начальному ¿-элементному участку (¿о, ¡¡, ..., рекуррентной

последовательности определить элемент этой же последовательности ¡„ е СЬ'(р), отстоящий от нулевого яо элемента на и шагов. Второй вариант аналитического решения линейных МРУ на основе двойственного базиса поля &?(рк), в отличие от первого, позволяет по произвольному ¿-элементному участку (л,, 1,4.1) и известному

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

Что касается матричного метода решения линейных МРУ, то следует отметить его недостаток, состоящий в том, что начальная фаза рекуррентной последовательности определяется путем вычисления каждого из элементов а] вектора [ао 01 аг ... в

отдельности, тогда как в первых двух методах элемент с =е" вычисляется в целом.

По сложности реализации наиболее простым является метод, основанный на применении двойственного базиса поля ОТ(рк).

Таким образом, при решении дальнейших задач предпочтение отдано варианту решения линейных МРУ на основе двойственного базиса поля

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

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

Показано, что свойством «зеркальности» обладают последовательности Гоулда длиной (2"-1), образоваппые парой примитивных многочленов степени и, двойственных относительно друг друга. Для таких «зеркальных» последовательностей Гоулда справедливы следующие, доказанные в работе, свойства.

Свойство 3.1. В любой, замкнутой в кольцо, двоичной «зеркальной» последовательности Гоулда с периодом (2" - 1) всегда будет иметь место так называемая зеркальная точка, т.е. такой элемент яь в противоположные стороны от которого будут формироваться одинаковые подпоследовательности длиной (2°"' - 1).

Свойство 3.2. Для любой «зеркальной» последовательности Гоулда (.ад... ¡к... с начальными элементами С - е' для М-последовательности А и О = ¿1' = е~' - для М-последовательности В «зеркальная» точка находится на расстоянии к шагов от начала, где значение к равно: Ю.

к = (2 -1) - ~ - для четного (/+/);

, (У

к = 2 ~ "ля нечетного (1+7),

где! и]могут принимать значения от 0 до (2" - 2).

Свойство 3.3. Всегда можно для заданного начального элемента С (или О) одной М-последовательности найти такой взаимный начальный элемент В (или С) другой М-последовательности, чтобы «зеркальный» элемент последовательности Гоулда находился ровно в её середине, т.е. к= 2"'1 -1.

Свойство 3.4. Элемент двоичной последовательности Гоулда, соответствующий «зеркальной» точке, всегда равен 0.

Свойство 3.5. "Зеркальные" последовательности Гоулда всегда будут иметь чётный вес.

Свойство «зеркальности» последовательностей Гоулда может быть использовано для выбора адресных и фазирующих комбинаций в системах телекоммуникаций.

Интересные корреляционные свойства ЛРД-последовательностей и большая их длина делают такие последовательности особенно полезными для измерения дальности до объекта..

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

Основной научный результат гл.З можно сформулировать следующим образом: Если характеристический многочлен Р(х) степени т представляет собой произведение нескольких минимальных многочленов f,{x\ f/x),..., f:(x), то элементы составной рекуррентной последовательности представляют собой сумму функций-след по этим многочленам, т.е.

s„=Tl(Ce")+TJ(DM") + ...+Tz(E7"), (15)

где е, корни многочленов f(x), fj(x)..... f2(x) соответственно. При этом

коэффициенты С, D,..., Е могут быть определены по произвольному т-элементному безошибочному участку составной рекуррентной последовательности {s} с использованием коэффициентов двойственного базиса ap,ßp,...,Xp, /7 = 1,..., т,

вычисленных для корней е, рг,..., у многочленов/,(х), fj(x),... ,/z(x) соответственно.

Таким образом, для декодирования составных рекуррентных последовательностей, так же как и для М-последователыюстей, может быть применен мажоритарный принцип.

Из выражения (15) следует вывод, что устройство, генерирующее составную рекуррентную последовательность, просто реализуется модулярными генераторами,

соответствующими минимальным многочленам ß(x), f}(x)...../Ах). При этом каждый из

генераторов параллельно формирует соответствующую М-последовательность, которые складываются по модулю простого поля GF(p) (чаще всего по модулю 2), образуя тем самым составную рекуррентную последовательность.

К числу составных последовательностей, рассмотренных в гл.З, относятся также инверсные рекуррентные последовательности: М-последователыюсти, последовательности Гоулда, ЛРД-последоватнльности.

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

В работе показано, что прямая рекуррентная последовательность и ее инверсная последовательность могут рассматриваться как последовательности, порождаемые одним и тем же характеристическим многочленом Р{х)=(1+х)Р\(х) и удовлетворяющие одному и тому же рекуррентному соотношению. Следовательно, обе они относятся к одному классу составных последовательностей и могут обрабатываться одним и тем же устройством с использованием двойственного базиса.

В четвертой главе диссертации разработаны основы реализации алгоритмов обработки рекуррентных последовательностей над полем GF(pk). Рассмотрены все традиционные операции обработки рекуррентных последовательностей, которые сводятся к выполнению алгебраических действий над элементами копечного поля: умножению, делению и обращению элементов.

К числу новых результатов четвертой главы относятся:

1) реализация процедуры формирования двойственного базиса шля GF(p');

2) реализация процедуры нахождения функции-след элемента поля;

3) аналитический метод реализации операций логарифмирования и ангилогарифмирования над элементами поля;

4) преобразование элементов поля ОГ(р1) в соответствующие элементы линейной рекуррентной последовательности (через функцию-след) и обратное преобразование элементов рекуррентной последовательности в элементы поля;

5) алгоритм упрощенной реализации умножения на двоичную матрицу. Рассмотрим подробнее результаты четвертой главы, имеющие новизну. Формирование двойственного базиса поля. Как показано в гл. 2 диссертации,

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

реализации этого метода и, в частности, формирования самого двойственного базиса. В соответствии с теоремой 2.2 двойственный базис (о^,со2,...,ак) по отношению к

произвольному степенному базису (г,",г-"+1,...,£-"+'"1)поля

где е -

первообразный корень, определяется выражениями (9) и (10).

Двойствешплм базисом по отношению к левому степенному базису (!,£,...,£•* ') будут постоянные коэффициенты (а1,а1,...,ак), которые вычисляются по формуле (10).

Устройство формирования элементов а, легко реализуется с помощью регистра сдвига на к ячеек памяти и схемы деления на производную Г"(е) (рис 1 ,а). При этом, на вход регистра с каждым тактом подаются поочередно коэффициенты характеристического многочлена/'(х), начиная с коэффициента ра по рц включительно. Для получения двойственного базиса (а\,аг,...,о)к)по отношению к произвольному

степенному базису (е",е"*1.....е"*к"') необходимо найденные коэффициенты а, умножить

на обратный элемент поля е~". Тогда схема формирования произвольного двойственного базиса будет иметь общий вид, представленный на рис. 1,6.

а) б)

Рис. 1. Структурная схема формирователя двойственного базиса по отношению клевому степенному базису а) и произвольному степенному базису поля б)

Реализация процедуры нахождения фунщии-след. Как известно, следом элемента е' б ОТ-Хр*) называется функция Т(е'), представляющая собой сумму:

Г(Е') = £' + (с')р + (Е') +... + Се')= £ (е')У ,

и>

В соответствии с методикой, изложенной в разделе 2.3. диссертации, след Т(е') равен

Г(8') = [а]0о, (16)

где [а]-= (ао а\ аг... ан) - векторная запись элемента поля б', а матрица во в общем виде представляет собой первый (младший) вектор-столбец матрицы 9, определяемой выражением (14).

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

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

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

Известный ученый в области теории кодирования Э. Берлекэмп в своей книге «Алгебраическая теория кодирования» отмечает, что если бы был «....известен некоторый метод, позволяющий легко вычислять логарифмы элементов поля (основанный не на просмотре таблиц, а на операциях над координатами двоичных представлений элементов поля), то логарифмический подход мог бы составить основу экономной реализации операций умножения и деления. В общем случае, однако, не известно никаких простых методов непосредственного вычисления логарифмов».

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

на основе операции над координатами двоичного представления элемента поля е' и его степени. Диссертантом совместно с его аспирантом В.Н. Сюршшм предложен метод вычисления логарифма и антилогарифма в полях Галуа [9], суть которого заключается в следующем.

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

Показано, что предложенный метод позволяет решить и задачу логарифмирования, т.е. существуют функционалы, которые по заданным координатам7о,/ь ...,/¡¡-1 определяют

координаты у0, VI.....у,ы двоичной записи числа г. При этом полученные функционалы

Ф//о,/ь ...,/к-1) также представляют собой полиномы Жегалкина.

В результате проведенного анализа доказано следующее следствие: При решении задачи логарифмирования в полях йР(^) каждая координата V} может быть определена, по крайней мере, двумя полиномами Жегалкина от переменных/о, /¡, ...,/кч.

В диссертации, в качестве примера, получены конкретные уравнения (полиномы Жегалкина) для аналитического нахождения логарифмов и антилогарифмов в поле ОД24) с образующим многочленомР(х) =1+х+х*.

Таким образом, в диссертационной работе показано, что операции логарифмирования и антилогарифмирования имеют аналитическое решение в вцде полиномов Жегалкина.

Анализируя полученные результаты по аналитическому решению задачи логарифмирования и ашилогарифмирования в полях

можно сделать вывод, что

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

Алгоритм упрощенной реализации умножения на двоичную матрицу. Во многих случаях при решении задач по обработке рекуррентной последовательности над полем СР(2к) необходимо выполнять действия по умножению на матрицу. Для упрощения реализации умножителя на двоичную матрицу, имеющую большее число единиц, чем нулей, можно рекомендовать алгоритм, впервые изложенный в описании изобретения [22]. Суть алгоритма сформулирована в виде следующей, доказанной в диссертации, теоремы: Если результатом умножения вектора (а0 а, а2 соответствующего

элементу в' поля йР(2*), на степень сопровождающей матрицы Р', отображающей элемент е' того же поля, будет вектор(Ь0 ...Ьк А),то такой же вектор будет получен при умножении вектора (а0а1а2 на инвертированную матрицу Р] при условии,

что вес со вектора (а0 а, аг ...акА) будет четным.

Если же вес а будет нечетным, то в результате улможения вектора (а^.Ор на инвертированную матргщу Р' будет получен вектор (Ьо,Ы,...,Ьк-\),

инвертированный по отношению к вектору (Ь0,1\,..., Ьк_1).

Показано, что описанный алгоритм позволяет также упростить умножение двоичного век-гора (а0,а1,...,а1_,) на матрицу Н, если в ней будут инвертироваться не все столбцы, а только те, которые имеют много единиц (больше половины).

Таким образом, материалы гл.4 являются основой как для аппаратной, так и для программной реализации алгоритмов обработки рекуррентных последовательностей над полем СР(рк) на основе двойственного базиса. Результаты четвертой главы были использованы аспирантами Д.С. Кукуниным и С.С. Владимировым для построения «калькуляторов Галуа», реализующих все действия над элементами поля ).

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

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

1. Для «закрепленной» фазовой точки при заранее известных значениях начальных элементов:

-поиск и выделение регулярно передаваемой комбинации цикловой фазы (КЦФ) в

синхронных системах передачи данных; -выделение «своей» адресной комбинации в синхронной многоадресной системе связи.

2. Для «закрепленной» фазовой точки при неизвестных значениях начальных элементов последовательности:

-декодирование кодовых комбинаций как рекуррентных последовательностей в

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

3. Для «незакрепленной» фазовой точки при заранее известных значениях начальных элементов последовательности:

-поиск и выделение комбинации цикловой фазы в асинхронных системах передачи данных;

-выделение «своей» адресной комбинации в асинхронно-адресной системе связи; -обработка рекуррентной последовательности при измерении дальности до объекта.

4. Для «слабозакрепленной» фазовой точки при неизвестных значениях начальных элементов последовательности:

-передача данных с относительным изменением фазы рекуррентной последовательности в квазисинхронных системах связи.

5. Оценка качества каналов передачи данных.

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

Именно этим вопросам и посвящена вторая часть диссертационной работы.

В пятой главе проанализированы различные алгоритмы декодирования комбинаций эвидистантного циклического кода (М-последователыюстей). Все рассмотрешше в главе алгоритмы относятся к системам с «закреплённой» фазовой начальной точкой.

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

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

Рассмотрены также более простые в реализации мажоритарные алгоритмы декодирования эквидистантных кодов. Одним из них является мажоритарная обработка на основе ортогональных проверок Дж. Месси. Рассмотрены также варианты алгоритмов мажоритарной обработки М-последователыюстей, предложенные в работах И.А. Новикова (в соавторстве) и A.A. Григорьева.

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

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

В соответствии с разработанным в гл. 2 алгоритмом начальный элемент ceGF(//), как информационный, определяется по произвольному ¿-элементному участку (snAi+i,-A+i-i) последовательности {s} через базис (coi,c02„...cüi), двойственный по отношению к степенному базису (s", s"+1,... е"4*'1) (формула (9)).

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

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

Наиболее близким прототипом разработанного алгоритма является мажоритарный алгоритм A.A. Григорьева Однако, реализация предложенного в диссертации мажоритарного алгоритма декодирования М-последовательносги на основе использования двойственного базиса поля GF(2*) существенно проще. И этот выигрыш тем больше, чем больше значение к.

К числу новых результатов, полученных в гл. 5, является разработка алгоритма декодирования децимированных комбинаций эквидистантного циклического кода с использованием двойственного базиса шля GF(pk). Операция над последовательностями, названная децимацией или разрядкой, была предложена С. Голомбом. Исследованиям этой операции посвящены также работы Н. Цирлера, В. Arazi, Д. Сарвате и М. Персли.

В гл. 5 диссертации показано, что, используя двойственный базис и обработав последовательность {у}, полученную из М-последовательности {й} путем децимаций с индексом д, по тому же алгоритму, что и последовательность {я}, получим элемент с» определяющий начальную фазу {\}, то есть

с. = ¿>Л«-,; ОР(Д (17)

1=1

Показано, что по найденному элементу с„ однозначно находится и элемент с, определяющий начальную фазу последовательности {.?}, из следующего выражения:

с = (с„)'; СЛ(рк). (18)

Таким образом, интересующий нас элемент с е может быть определен в

результате обработки не только принятой М-последовательности {$}, но и еще (¿-1) последовательностей полученных из последовательности путем децимаций с индексами децимаций ^ = р', г = 1, 2, ..., (¿-1). Этот факт может быть использован для повышения достоверности декодирования эквидистантного кода.

Рис. 2. Результаты моделирования декодирования эквидистантного кода методом двойственного базиса при вероятностях ошибки: 0,2 - а; 0,3 — б

В качестве примера (рис. 2) приведены результаты моделирования декодирования эквидистантного кода с характеристическим многочленом Р(х) - х84х4+.х3+л;2+1. Начальной фазой в данном примере является элемент поля e,2S. Очевидно положительное влияние децимаций на качество декодирования - каждая следующая децимация с индексом q-2z заметно повышает достоверность результатов.

Результаты моделирования различных методов декодирования эквидистантных кодов как рекуррентных последовательностей с характеристическим многочленом Р(;с)=х4+л:+1 приведены на рис. 3. Псевдослучайные последовательности искажались всевозможными полиномами ошибок (полный перебор), а затем декодировались различными методами. На основании результатов моделирования можно сделать вывод о преимуществе декодирования с использованием двойственного базиса поля Галуа, прежде всего, по корректирующей способности. Это достигается за счёт исправления значительной доли ошибок, кратность которых превышает 0,5(dmn -1). При этом повышение достоверности достигается благодаря применению децимаций.

Вероятность битовой ошибки в канале, pQ

Рис. 3. Вероятность правильного декодирования эквидистантного кода (15,4)

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

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

Элементами М-последовательносга {s} над полем с двойным расширением GF((р*)1") являются вычеты по тройному модулю modd[P(jc),G(a)j>], где Р(х) - неприводимый над полем GF(p*) многочлен степени т и СЦа) - неприводимый над полем GF(p) многочлен степени к. Таким образом, элементы поля GF((ркУ) в полиномиальном представлении являются многочленами R(x)= r„-jx!"'l+ r„-2Xm~2 +... + r^+rn, где коэффициенты rh i=0,l,...,(m-l), являются элементами поля GF(р1).

Пусть, например, р=2, G(a)W+a+l, (к=3); P(xy=pax2+pix+p2=x2+x+(l+a), (т=2). В этом случае элементы М-последовательности с периодом N=pmt~l=63 будут удовлетворять рекуррентному соотношению s„ = -р^ш-рА-г = Sn-i+a3s„-2. Корнями многочлена P(x) являются ^-сопряженные элементы поля GF((p3)2), где q=2>. Обозначим один из корней е, тогда второй корень будет е8. Тогда в соответствии с (10) коэффициенты двойственного базиса будут равны:

а2=-£- = 1; а1=-£-+а,е = с' = 1+s. Р'(е) ' Р\е) 2

Выбрав в качестве исходных членов рекуррентной последовательности (itt,si)=(0,l), можем определить, в соответствии с (7), образующий элемент с М-последовательности {s}:

c = a1s0+a2s, = a2=l.

Определив с, можно теперь по формуле (6) найти значение произвольного элемента s„. Например, ло= Т(с £10)= £,0+( е10)8=а5=1 +а.

Показано, что тот же образующий элемент с может быть определен по произвольному участку (зд+i) последовательности {s}. Это позволяет осуществить мажоритарное декодирование комбинаций эквидистантного циклического кода над конечным полем с двойным расширением.

Показано также, что разработанный алгоритм применим для декодирования в конечном поле с двойным расширением комбинаций {v} с элементами Vj=j?„ полученными из {s} путём децимации с индексом децимации д=8.

Таким образом, для данного примера можно сформировать эквидистантный код (М-последовательности) с минимальным кодовым расстоянием dirun = (q -1 )q= 56.

Алгоритмы декодирования будут такими же как и в конечных полях GF(р ).

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

Шестая глава посвящена исследованию алгоритмов декодирования циклических кодов БЧХ и Рида-Соломона на основе двойственного базиса. При этом кодовые комбинации, как рекуррентные последовательности с характеристическим многочленом Р(х) степени т, представляют собой двойственный (или дуальный) код по отношению к классическому циклическому (л,/я)-коду с порождающим многочленм G(x) = х"-1 /Р(х), где п - порядок корней примитивного многочлена степени к, образующего поле GF(p ). Обоим вариантам представления кода соответствуют одни и те же комбинации, поэтому рассматриваемые двойственные циклические коды БЧХ и Рида-Соломона, как рекуррентные последовательности, названы эквивалентными с аббревиатурой БЧХЭ и РСЭ.

Применяемые в настоящее время алгоритмы декодирования кодов БЧХ и PC в большинстве основаны на вычислении синдромов принятой комбинации, определении коэффициентов многочлена локаторов ошибок, нахождении ошибочных позиций в комбинации с использованием процедуры Ченя, определении значений ошибок (для недвоичных кодов) и исправления ошибок в принятой комбинации. Наиболее сложным является решение ключевого уравнения. Известны такие алгоритмы решения ключевого уравнения как алгоритм Берлекэмпа-Месси, алгоритм Евклида и алгоритм прямого решения системы линейных уравнений, часто называемый в литературе декодером Питерсона-Горенстейна-Цирлера.

Известны также алгоритмы декодирования кодов БЧХ и PC в частотной области, основанные на применении многочленов Мэттсона-Соломона, которые в некоторых литературных источниках названы дискретным преобразованием Фурье над полем GF(2 ).

Всем указанным выше алгоритмам декодирования кодов БЧХ и PC в той или иной мере присущи существенные недостатки, с которыми на практике разработчики оборудования вынуждены мириться. Одним из общих недостатков является то, что все они требуют предварительного вычисления синдромов. Это в свою очередь вносит задержку в процесс декодирования, связанную с накоплением всей кодовой комбинации до начала процесса декодирования. Второй недостаток состоит в том, что сложность реализации декодера в большой степени зависит от кратности исправляемых ошибок - чем большей кратности ошибки исправляет код, тем сложнее декодер. Это связано с решением системы линейных уравнений большего порядка. К недостаткам указанных алгоритмов можно отнести и то, что все они являются алгоритмами с так называемым «ограниченным расстоянием», т. е. они исправляют ошибки кратности t или менее для кода с кодовьм расстоянием i4in=2i+l. В этом отношении показательно следующее высказывание авторов известной книги по кодированию Дж. Кларка, мл. и Дж. Кейна: «Можно предложить алгоритмы, которые позволяют исправлять комбинации ошибок веса больше t, однако эти алгоритмы оказываются непрактичными ввиду своей сложности» и далее - «До сих пор не найдены алгоритмы декодирования, в которых используется эта дополнительная корретирующая способность» [Кодирование с исправлением ошибок в системах цифровой связи. -М.: Радио и связь, 1987].

Поэтому в гл. 6 были поставлены и решены следующие задачи:

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

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

- предложены принципы реализации кодирующих и декодирующих устройств кодов БЧХЭ и РСЭ на основе двойственного базиса;

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

Показано, что эффективность кодирования и декодирования кодов БЧХЭ и РСЭ повышается, если в качестве информационных элементов будут являться образующие коэффициенты С, D,...,E, которые однозначно соответствуют начальным элементам (S0S1.S2 ■-Sm-i) последовательности {s}. При этом декодирование будет осуществляться «в целом», поэтому отпадает необходимость в вычислении отдельных начальных элементов принимаемой кодовой комбинации, что уменьшает задержки декодирования. В диссертации доказано, что: «Коэффициенты C,D,...,E могут быть определены по произвольному т-элементному безошибочному участку составной рекуррентной последовательности {s} с использованием коэффициентов двойственного базиса ар,Рр,...,Хр, р = 1,.,.,т, вычисленных для корней е, ц...,у многочленовf,(x),fj(x), ...,fz(x) соответственно». Таким образом, для декодирования циклических кодов БЧХЭ как составных рекуррентных последовательностей, так же как и для эквидистантных кодов (М-последовательностей), может быть применен мажоритарный принцип.

Корректирующие способности кодов БЧХЭ могут быть усилены вследствие обработки на основе двойственного базиса децимированных комбинаций кода БЧХЭ. Этот вывод вытекает из следующей доказанной в гл. 6 теоремы:

Теоремы 6.1. Если элементы С,,...,С. еGF(2l) однозначно определяют начальную фазу рекуррентной последовательности {s} кода БЧХЭ, то начальная фаза последовательности {v} полученной из {sj путем ее децимации с индексом

g = 2', i = 0Д,...,(£-1), будет определяться элементами

Коатность ошибок

-о- без децимаций -о— 1 децимация -а- 2 децимации —3 децимации

Рис. 4. Доли исправляемых ошибок кодом БЧХЭ (15, б) с образующим многочленам

Благодаря мажоритарной обработке принятой и децимированных последовательностей код БЧХЭ способен корректировать значительную долю ошибок, кратность которых превышает половину минимального расстояния по Хеммингу. Например, доля исправляемых трёхкратных ошибок кодом БЧХЭ (15,6) с 4шп=6 без учёта децимаций составляет около 23%, а при декодировании с учётом всех децимаций - около 63% (рис. 4).

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

Сравнение вероятностей правильного декодирования кодов (15,7) и (31,15) корреляционным методом (КМ), табличным методом (ТМ) и алгебраическим синдромным методом (СМ) для классического кода БЧХ и методом двойственного базиса (МДБ) для кода БЧХЭ представлено на рис. 5. Из графиков видно, что применение метода двойственного базиса в сочетании с децимациями для данных кодов позволяет получить достоверность не ниже, чем декодирование другими методами (КМ, ТМ и СМ).

Рп

МДБ

2=0

7=2 КМ /V

ТМ / \

см ^ -

2=4

МДБ г=0 /Щ **

2-\^

тм / \ 1 \ !

см \!

а)

б)

Рош

КГ*

10"'

Рис. 5. Вероятности правильного декодирования Р„ кодов БЧХ (КМ, ТМ, СМ) и БЧХЭ (МДБ): а-(15,7); 6-(31.15)

Одним из критериев сложности реализации алгоритмов декодирования является емкость необходимой памяти при программной реализации. В работе проведен сравнительный анализ (рис. 6) алгоритмов по количеству требуемой памяти для наиболее ресурсоёмких процессов декодирования на примере двух вариантов кодов - (15,6) и (31,16).

Кратность ошибок

-ИНИН -МДБ^Н

а)

1.0Е+07 1.0Ё+06

1 1.0Е+05-

2 п с

£ 1.СЕ+04 О

0

1 1.0Е+Ш Ш

1,06+02 1.0Е+01 •

Кратность оим бок

—Ж—ТМ ——МДБ-ДН

-» СМ ■ Дек. Мегтота »— МДЬ-СН

б)

Рис. 6. Емкость требуемой памяти для кодов БЧХ: а - (15,6) и б-(31,16)

Анализ показал, что метод двойственного базиса с динамическим накоплением (МДБ-ДН) результатов декодирования по требуемой емкости памяти сравним с синдромным методом (СМ, Пигерсона-Горинстейна-Цирлсра), тогда как методы КМ и ТМ, декодер Меггита и метод двойствешюго базиса с статической памятью (МДБ-СН) требуют значительно большей емкости памяти, особенно с увеличением длины кодовой комбинации и кратности исправляемых ошибок.

В гл. 6 рассмотрен также алгоритм декодирования дуальных кодов Рида-Соломона как рекуррентных последовательностей па основе двойственного базиса Проведенный анализ показал, что двойствешшй базис также обеспечивает повышение эффективности декодирования кодов РСЭ, как рекуррентных последовательностей, вследствие применения мажоритарной обработки и децимаций над принятой последовательностью. Однако, возможность применения децимаций по отношению к принятой кодовой последовательности предъявляет определенные требования к характеристическому многочлену Р(х), которые в работе сформулированы в виде следующего свойства 6.1: Комбинации циклического кода РСЭ над полем GF(pk) могут быть мажоритарно декодированы с использованием децимаций, если характеристический многочлен Р(х) представляет собой один или произведение нескольких полиномов f,(x), входящих в

разложение двучлена (хр -1) на неприводимые полиномы деления круга.

Для кодов РСЭ с таким многочленом Р(х) справедливы доказанные в работе две теоремы, одна из которых названа теоремой идентичности (инвариантности), а другая -теоремой однозначности.

Теорема 6.2 (Теорема идентичности). Если характеристический многочлен Р(х) представляет собой один или произведение нескольких минимальных многочленов, входящих в разложение двучлена (хр'~] -1), то исходная рекуррентная последовательность = 2), образованная по многочлену Р(х), и

последовательности {и} = (и^щи,..!!^ 2), полученные из {s} путем децимаций с

индексами q-p', где j = 1, 2, ... , (к - 1), будут удовлетворять одному и тому же рекуррентному уравнению (соотношению).

Теорема 6.3 (Теорема однозначности). Если элементы А, В, С,... е GF(p"), соответствующие сомножителям /(лг) характеристического многочлена Р(х), однозначно определяют начальную фазу рекуррентной последовательности {j}, то начальная фаза последовательностей {и}^, полученных из последовательности {j} путем

ее децимации с индексами q = р', где j = 1, 2, ... , ß - 1), также будет однозначно определяться теми же элементами А, В, С, ..., но имеющими циклический сдвиг вправо на j шагов.

Именно эти особенности и позволяют усилить корректирующие свойства кода РСЭ при мажоритарном декодировании кодовых комбинаций как рекуррентных последовательностей с учетом децимаций.

В результате проведенного в диссертации исследования вявлено следующее характерное свойство 6.2 кодов РСЭ: Если для построения кода РСЭ (п,к) над полем GF(2k) выбран в качестве характеристического примитимный многочлен Р(х) степени к, то минимальное кодовое расстояние для такого кода, как и для двоичной М-последовательности такого же периода, будет равно dmn = 2k~\ тогда как классические (п,к)-коды Рида-Соломона с несопряженными корнями многочлена Р(х) имеют минимальное кодовое расстояние dmm =л ~k+l.

Весовой спектр для кодов (15,4) приведен на рис. 7, из которого видно, что в коде РСЭ с примитивным многочленом Р(х) (код 1, чёрные столбцы) 225 комбинаций имеют вес, равный 8, другие комбинации имеют веса 12, 14 и 15. Заштрихованные столбцы соответствуют весам второго (15,4) классического кода РСЭ (код 2), у которого dmi„ = 12.

5

о

о о

ID

о m о

5 * S ä

et о

о

5

40000

30000 -

20000

10000

8

-1

10 11

12 13 14 15

Вес кодовых слов, w

■ Код 1 И Код 2

16

Рис. 7. Распределение весов кодовых слов для кодов Рида-Соломона; Код 1 ~{IS,A) с многочленом Р(х) = (.х + £)(х+£2)(;г + г4)(х + £-8)= х< + t Код 2 - (15,4) с многочленом Р(х) = (х + 1)(х + £)(х + £г )(х+£г) = jc1 + V + <f V + х + е6.

Зависимость доли и вероятностей правильно декодируемых комбинаций кода I (при различном числе децимаций) и кода 2 от кратности ошибок показана на рис. 8 и 9.

Кратность ошибки

Рис. 8. Доля правильно декодированных ошибочных комбинаций кода 1 и кода 2 РСЭ (15,4) при использовании алгоритма на основе двойственного базиса

Вероятность ошибки в канале, р0

Рис. 9. Вероятность правильного декодирования ошибочных комбинаций кода 1 и кода 2 РСЭ (15,4) при использовании алгоритма на основе двойственного базиса

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

В диссертации приведены также зависимости от кратности ошибок долей комбинаций и вероятностей неправильного декодирования, а также отказов от декодирования. Разработан алгоритм декодирования методом двойственного базиса с динамическим накоплением (МДБ-ДН), который требует значительно меньше памяти дм накопления результатов мажоритарного декодирования, а также разработаны принципы построения кодирующих и декодирующих устройств циклических кодов БЧХЭ и Рида-Соломона, декодирование которых ведется с использованием двойственного базиса.

Оценивая оперативность методов декодирования отметим, что для декодеров на основе классических методов (КМ, ТМ и СМ) основной процесс декодирования начинается после полного накопления принимаемой комбинации, в то время как декодирующее устройство по методу двойственного базиса (МДБ) производит обработку уже первого принятого т-элементного участка (л,т)-кода и далее с поступлением из канала каждого нового информационного элемента. При этом для МДБ возможно завершение процесса декодирования еще до окончания приема кодовой комбинации. Так, при отсутствии ошибок декодирование можно завершить после приема [0,5(л+1) + от-1] элементов.

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

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

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

Зависимости от вероятности ошибки в канале без памяти среднего времени, необходимого для поиска и успешного распознавания комбинации циклового фазирования, представляющей собой М-последовательность с периодом Л<=15 и длиной зачетного участка £=12, изображены на рис.10. Из графиков видно, что метод двойственного базиса обеспечивает по сравнению с двумя другими методами меньшее время поиска и успешного распознавания КЦФ как рекуррентной последовательности.

Вероятность ошибки (р)

Рис. 10. Среднее время поиска и выделения К11Ф для различных методов

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

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

В методе согласованного фильтра использован параметр К, определяющий порог допустимого количества ошибок в принятой кодовой комбинации. Для метода двойственного базиса параметром является длина зачетного участка Видно (рис. 11, а), что для согласованного фильтра наибольшая вероятность правильного обнаружения фазы Рпф достигается при К = 8. Для двойственного базиса (рис. П, б, в) лучшими показателями можно считать 1=10 для однофазной и 1 = 1 для двухфазной КЦФ.

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

Другой отличительной особенностью метода на основе двойственного базиса является, как показано в диссертации, достаточно малая вероятность ложного фазирования Рлф для соответствующих значений Ь. При вероятности ошибки ро<0,05 метод на основе двойственного базиса соизмерим по данному показателю с методом согласованного фильтра. Применение двухфазных КЦФ позволяет значительно уменьшить вероятность ложного фазирования по сравнению с использованием одной фазы, однако при этом возрастает вероятность необнаружения фазы.

Главными преимуществами метода циклового фазировыания на основе двойственного базиса является простота алгоритма и сравнительно малое время фазирования.

2 4 6 8 10 11 12 К

0.1 0.01 й "" - ------ .31- — * ----"Г;--- Л,ш=<М>5 о—=0.1

Д.«=ВД5 х - Рош^О,2 ¡>„..=0,25

ж

0.001

Рпф а)

1 7 8 10 12 14 15 16 1

" Л,ш=<М>5 - *----------п__=ои

0.1 ..... " -« рош=0,15 -----з АжНи

'—_ ----к р„ш=0,25

£101

Япф Я

1 5 6 7 8 9 £х2

----.— -с - _________ ••.....& . —-—-НИ />ош=0,05

0.1 0.01 №---- ...........?________ - ______—_____________ " --Ж РоиГ^Л

----------- Рош=0,15 РошГ^Л

рош=0,25

О.001 • р„ф

в)

Рис. 11. Вероятность правильного фазирования Р„ф при декодировании 104участков различными методами: согласованный фильтр (Р(х)=х5+х3+1) - а: двойственный базис с одной фазой (Р(х)=: к5+х3+1) -б; двойственный базис с двумя фазами (Р(х)=х4+х+1) - в

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

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

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

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

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

Рассмотрим кратко результаты проведенного в гл. 8 анализа.

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

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

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

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

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

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

В диссертации приведена структурная схема, реализующая предложенный алгоритм декодирования, а также пример работы такой системы. На устройства для передачи и приема данных с относительным изменением фазы рекуррентной последовательности автором в соавторстве получены авторские свидетельства [14 - 17].

Задача 3. В большинстве случаев взаимодействие между различными сетевыми узлами или оконечными устройствами в распределённых сетях осуществляется на основе локальных адресов. Наиболее часто в качестве адресных выбирают рекуррентные последовательности различной структуры. К ним относятся М-последовательности, последовательности Гоулда, ЛРД-последовательности и др.

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

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

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

Задача 4. Оценка качества канала передачи данных - одна из актуальнейших задач.

Недостатками многих методик оценки качества канала передачи данных являются:

- занятие канала и невозможность передачи данных во время проведения измерений;

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

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

В случае наличия ошибок в канале количество выделенных элементов с', соответствующих начальной фазе, при обработке от-элементных участков последовательности будет уменьшаться за счет появления других (ложных) элементов d ф е' (рис. 2). С увеличением рош снижается максимум С, за счет увеличения количества других «ложных» выделенных Q, т.е.,образно выражаясь, с ростом вероятности ошибки в канале «растёт лес ложных деревьев». Этот фактор и используется в диссертации для оперативной оценки качества канала передачи данных, в частности по вероятности ошибки.

Автором совместно с его аспирантом Д.С. Кукуниным разработана методика оценки качества канала по среднему значению отклонения Д между максимальным накопленным значением (pi одного элемента (СО и ближайшим к нему по величине значением <рз другого элемента (Сг), т.е. А = <pi — Фг. При этом определяется доверительный интервал (рат,„ + Ротюд, в котором с доверительной вероятностью Рда находится вероятность ошибки рош в канале. Зависимости pomin и рот» от длины выборки M-Nn в двоичных элементах для кода БЧХЭ (15,11) прирот = 0,01 и 0,1 представлены на рис. 12, где//- длина выборки в числе кодовых комбинаций.

В заключение можно отметить, что рассмотренная методика основана на величине Д, одно значение которой измеряется в результате обработки одной кодовой комбинации рекуррентного кода. По виду рис. 2 очевидно, что для оценки качества канала, в частности вероятности ошибки, можно использовать и другие более быстрые критерии. Одним из таких критериев в работе выбрана частость появления новых «деревьев в лесу», т.е. новых ложных выбросов относительно максимального значения элемента С;, выделенного в результате обработки »¡-элементных участков кодовой комбинации. При этом уже по одной замкнутой в кольцо кодовой комбинации можно приближённо оценить вероятность ошибки в «плохом» канале (ро> 10~2).

В реальных каналах сро< 10~3 вероятность ошибки может оперативно оцениваться путем деления суммарного количества ложных «деревьев» на произведение (т -М), где М -длина выборки в кодовых элементах. Такой метод будет наиболее эффективным.

, м

Рис. 12 Определение границ ро,™ ирглтх для Рю=0,95 при декодировании комбинаций циклического кода БЧХЭ (15,11)

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

Девятая глава посвящена вопросам применения двойственного базиса для обработки числовых рекуррентных рядов в бесконечном поле. Проведен анализ числовых последовательностей чисел Фибоначчи, чисел Люка и обобщённых р-чисел Фибоначчи, обозначаемых в общем виде как {(?} — (Со С; С; С/з С/4 С?б Сп Се...), которые удовлетворяют одному и тому же рекуррентному уравнению второго порядка

0,= 0м + 0и,/> 2. (19)

Соответствующий характеристический многочлен «золотой пропорции» Р(х) будет:

Р(х)=р0х2+р1х+р2=х1-х-1. (20)

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

а а =_£«_ = 1 Р\е,) 2л/? 2 П*,) VI' (21)

о = Р\+Р<,ег о __ Ро = -1

Пе2) " 2^5 ' Рг Р\ег) V? где Е1 и Ег - корни многочлена Р(х).

В зависимости от значения начальных членов Go и Gi рекуррентной последовательности {G} могут быть найдены такие числа А и В, которые позволяют определить произвольный элемент G, этой последовательности из следующего выражения:

G,=Ati'+ Bzi. (22)

В соответствии с разработанной автором методикой коэффициенты А и В могут быть найдепы по любому ш-элементному (т=2) участку (G,G,+i) последовательности {G} с «закрепленной» начальной точкой, т.е. с известным значением п, а именно:

А = е;'(аД+агам), В = (ß,G + ß2GJ. (23)

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

С помощью двойственного базиса проанализированы рекуррентные последовательности обобщённых р-чисел Фибоначчи (по А.П. Стахову) с характеристическим многочленом Р(х) -У-1 для р = 2,3.

Наконец, в последней главе диссертации на основе двойственного базиса исследованы рекурсивные последовательности {а} второго порядка, члены которых будут удовлетворять рекурсивной функции общего вида:

а<=сЛ-,-с2а<-2> ' ^2, (24)

где а и С2 принадлежат множеству целых чисел в общем виде отличных от 1. К таким последовательностям относятся, в частности, и последовательности от-чисел Фибоначчи.

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

Свойство 9.1. Числовая рекурсивная последовательность {а} второго порядка, корни характеристического многочлена которой не кратные и являются комплексными сопряжёнными числами типа />(cosO±/sinO), будет периодической, если G - делитель 2л.

При этом длина периода N = 2л / 9.

Свойство 9.2. Период рекурсивной последовательности, удовлетворяющей рекуррентному соотношению а, = а,., - , с чётным значением N содержит два полупериода длиной N/2 с одинаковыми числовыми значениями, но с противоположными знаками.

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

В заключительной части гл. 9 рассматривается проблема построения помехоустойчивых кодов над полем рациональных чисел на основе применения рекуррентных последовательностей чисел Фибоначчи. Показана возможность использования двойственного базиса при декодировании систематических корректирующих (п. к) кодов, исправляющих однократные ошибки, при этом число избыточных элементов кода будет равно (п-к) = 2 независимо от длины комбинации п, а минимальное кодовое расстояние ^„ = 3.

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

Приложение содержит значения коэффициентов двойственного базиса поля GF(2l) относительно левого степенного базиса для примитивных многочленов Р(х) до 12-й степени включительно.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

• при измерении дальности до объекта;

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, включенных в Перечень ВАК для докторских диссертаций или находившихся в этом перечне на момент опубликования

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

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

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

4. Когновицкий О.С. Методика оценки качества канала при передаче рекурсивных последовательностей/ О.С. Когновицкий, Д.С. Кукунин // Труды учебных заведений связи / СПбГУТ. - СПб, 2007. -№ 176. - C.15S -165 (номер подписан в печать 15.12.2006).

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

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

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

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

9. Когновицкий О.С. Метод решения нелинейных уравнений для вычисления логарифма в полях Галуа/ О.С. Когновицкий, В.Н. Сюрин И Системы и сети передачи информации: сборник научных трудов учебных институтов связи / ЛЭИС. - Л., 1988. - С. 78-88.

10. Когновицкий О.С. Передача дискретных сообщений с помощью относительной временной манипуляции составных фазомашшулированных сигналов/ В.Н. Сюрин, О.С. Когновицкий, Ю.Б. Окунев // Теория передачи информации по каналам связи: Сборник научных трудов учебных институтов связи / ЛЭИС. - Л., 1984. - С. 80-85.

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

12. Когновицкий О.С. О реализации троичного циклического кода, исправляющего однократные ошибки.// Труды учебных институтов связи/ЛЭИС, - Л., № 72,1975, с. 10-18

13. Когновицкий О.С. Троичные циклические коды, исправляющие однократные ошибки// Труды учебных институтов связи/ЛЭИС. -Л., 1974. ,Vü 67. С. 99-105.

Авторские свидетельства СССР и патенты РФ

14. A.c. 642867 СССР, МКИ Н 04 L 17/00, Н 04 L 3/00. Устройство для передачи и приема дискретной информации / О.С.Когновицкий, В.Н. Сюрин, И.С. Михеев ; опубл. 15.01.79, Бюл. №2.

15. A.c. 886295 СССР, МКИ Н 04 L 17/0. Устройство для передачи и приема дискретной информации / О.С. Когновицкий, В.Н. Сюрин, А.Н. Глухов; опубл. 30.11.81, Бюл. № 44.

16. A.c. 886296 СССР, МКИ Н 04 L 17/00, Н 04 L 3/00. Система для передачи и приема дискретной информации/ О.С.Когновицкий, В.Н. Сюрин; опубл. 30.11.81, Бюл. № 44.

17. A.c. 1149428 СССР, МКИ Н 04 L 17/16. Устройство для приема дискретных сигналов /В.Н. Сюрин, О.С, Когновицкий, Ю.Б. Окунев ; опубл.07.04.85, Бюл. № 13.

18. A.c. 429543 СССР, МКИ Н 04 b 3/46. Устройство для автоматического измерения характеристик дискретного канала / О.С. Когновицкий, В.В. Гнилицкий ; опубл. 25.05.74, Кюл. № 19.

19. A.c. 535743 СССР, МКИ Н 04 В 3/46. Устройство для автоматического измерения характеристик дискретного канала / О.С. Когновицкий, В.В. Гнилицкий ; опубл. 15.11.76, Бюл. №42.

20. A.c. 660276 СССР, МКИ Н 04 В 3/46. Устройство для автоматического измерения характеристик дискретного канала / О.С. Когновицкий, A.B. Чулкин ; опубл. 30.04.79, Бюл. № 16.

21. A.c. 1504807 СССР, МКИ Н 04 В 3/46, Н 04 L II/08. Устройство для измерения характеристик дискретного канала связи / О.С. Когновицкий, Г.М. Марголин, A.B. Чулкин ; опубл. 30.08.89, Бюл. № 32.

22. A.c. 1716609 СССР, МКИ Н 03 М 13/02. Кодирующее устройство кода Рида-Соломона/ О.С. Когновицкий, A.B. Буданов, Г.П. Брызгина; опубл. 29.02.92, Бюл. № 8.

23. А. с. 1718385 СССР, МКИ Н 03 М 13/00. Устройство для декодирования кода Рида-Соломона/ A.B. Буданов, Г.П. Брызгина, О.С. Когновицкий, Н.П. Корнилова, А.П. Чепиков; опубл. 07.03.92, Бюл. № 9.

24. Пат. РФ № 2007040 (RU 2007040 С1), МПК 5 Н 03 М 13/00. Устройство для декодирования кода Рида-Соломона / О.С. Когновицкий, A.B. Буданов, Г.П. Брызгина, А.Б. Ельников ; зявл. 29.04.91 ; опубл. 30.01.94, Бюл. № 2.

25. Пат. РФ № 2007041 (RU 2007041 С1), МПК 5 Н 03 М 13/00. Устройство для декодирования кода Рида-Соломона / A.B. Буданов, А.И. Дементьев, А.Б. Ельников, О.С. Когновицкий, Н.П. Корнилова, К.Н. Певцов; зявл. 03.07.91; опубл. 30.01.94, Бюл.№ 2.

26. Свидетельство РФ о государственной регистрации программы для ЭВМ

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

Другие публикации

27. Монография. Когновицкий О.С. Двойственный базис и его применение в телекоммуникациях. - СПб.: Линк, 2009. - 411 с.

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

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

30. Когновицкий О.С. Основы циклических кодов: учеб. пос. /ЛЭИС. - Л., 1972. - 88 с.

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

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

33. Когновицкий О.С. Класс «зеркальных» последовательностей Гоулда // Труды учебных заведений связи / СПбГУТ. - СПб., 2008. - № 178. - С.6-12.

34. Когновицкий О.С. Метод обработки рекуррентных последовательностей в информационных системах // Международная НТК «Актуальные проблемы анализа и построения информационных систем и процессов»: сборник статей / Южный федеральный университет. - Таганрог, 2010. - С. 79-85.

35. Когновицкий О.С. Метод передачи данных, основанный на изменении фазы псевдослучайной последовательности // 4-я всесоюзная школа-семинар по вычислительным сетям. Часть 4. «Помехоустойчивое кодирование и сжатие данных»: сб. тр. - Москва-Ташкент, 1979.-С. 64-68.

36. Когновицкий О.С. Анализ рекуррентных последовательностей обобщённых чисел Фибоначчи с применением двойственного базиса // 1-й Международный копгресс «Современные аспекты математики гармонии и ее применение в экономике, естествознании, технологии, социуме и образовании»: докл. - Одесса, 2010.

37. Когновицкий О.С. Циклические коды Рида-Соломона как рекурсивные последовательности // X юбилейная Санкт-Петербургская международная конференция «Региональная информатика-2006)»: докл. / СПбИСУ. - СПб., 2007.

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

39. Когновицкий О.С. Метод вычисления логарифма в конечном поле GF(2m) /Когновицкий О.С., Сюрин В. Н., Ассанович Б. А.// 9-я всесоюзная конференция по теории кодирования и передачи информации «Корректирующие коды»: тез. докл. - Одесса, 1988. -С. 100-102.

40. Когновицкий О.С. Об одном алгоритме мажоритарного декодирования кодов максимальной длины // 9-я всесоюзная конференция по теории кодирования и передачи информации «Корректирующиекоды»:тез. докл.-Одесса, 1988.-С. 195-197.

41. Когновицкий О.С. Мажоритарная обработка дискретной ПСП при измерении запаздывания в спутниковых системах связи / О.С. Когновицкий, П.А. Смирнов // VII НТК «Оптические, сетевые и спутниковые сети и системы связи»: тез. докл. - СПб (г. Пушкин), 1996.-С. 108-109.

42. Когновицкий О.С. Фибоначчиева группа и проблемы помехоустойчивого кодирования над полем целых десятичных чисел / О.С. Когновицкий, М.Ю. Сергеева // 62-я НТК: мат-лы /СПбГУТ. - СПб., 2010. - С. 81-82.

43. Когновицкий О.С. Прямые и инверсные рекуррентные последовательности (М-последовательности, последовательности Гоулда и ЛРД) и их обработка с использованием двойственного базиса // 62-я НТК: мат-лы / СПбГУТ. - СПб., 2010. - С. 61-62.

44. Когновицкий О.С. Сравнительный анализ методов декодирования двоичных кодов БЧХ/ Д.С. Кукунин, О.С. Когновицкий // 61-я НТК: мат-лы / СПбГУТ- СПб.,/2009. - С. 46.

45. Когновицкий О.С. Недвоичные коды БЧХ (Рида-Соломона) как рекурсивные последовательности и их декодирование с использованием двойственного базиса // 61-я НТК: мат-лы / СПбГУТ. - СПб., 2009. - С. 45-46.

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

47. Когновицкий О.С. Сетевая версия калькулятора Галуа / Д.С. Кукунин, О.С. Когновицкий // 57-я юбилейная НТК: мат-лы / СПбГУТ. - СПб., 2005. - С. 25.

48. Когновицкий О.С. Реализационные основы применения двойственного базиса поля Галуа в задачах передачи и обработки данных // 54-я НТК: мат-лы / СПбГУТ. — СПб., 2002. -С. 21.

49. Когновицкий О.С. Метод алгебраического кодового разделения рекуррентных последовательностей с различными характеристическими многочленами // 51-я НТК: тез. докл. / СПбГУТ. - СПб., 1998.

50. Когновицкий О.С. Мажоритарное декодирование циклических кодов как рекуррентных последовательностей с разложимым характеристическим многочленом // 50-я НТК: тез. докл. / СПбГУТ. - СПб., 1997.

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

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

53. Когновицкий О.С. Об испытательных сигналах для каналов интегральной сети // Научно-техн. конф.: мат-лы / ЛЭИС.-Л., 1971.-Вып.2.-С.158-163.

Подписано к печати 23.12.2010 Объем 2 печ. л. Тираж 100 экз. Отпечатано в СПбГУТ. 191186 СПб, наб. р. Мойки,61

Введение.

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

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. Предложены новые, основанные на применении двойственного базиса, подходы к анализу числовых рекуррентных последовательностей (последовательностей чисел Фибоначчи, чисел Люка и др.) и принципы построения помехоустойчивых кодов над бесконечным полем целых чисел.

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

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

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

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

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

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

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

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.