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

На правах рукописи

Глухарев Игорь Николаевич

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Курск - 2004

Работа выполнена в Курском государственном техническом университете

Научный руководитель:

доктор технических наук, профессор ТипикинА. П.

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

Лопин В. Н.,

кандидат технических наук Старков Е. Ф.

Ведущая организация:

в/ч 25714 (г. Курск)

Защита состоится «¿4 » декабря 2004 г. в 1400 часов на заседании диссертационного совета Д212.105.02 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, конференц-зал.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу: 305040, г.Курск, ул. 50 лет Октября, 94, ученому секретарю диссертационного совета Д212.105.02.

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

Автореферат разослан «22. » ноября 2004 г.

Ученый секретарь

диссертационного совета

Титенко Е.А.

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

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

Качество цифрового канала определяется скоростью передачи данных и характеристиками ошибок в канале. Знание характеристик ошибок в каналах требуется при разработке и вводе в эксплуатацию контроллеров ВЗУ и аппаратуры передачи данных сетей ЭВМ, содержащих в своем составе систему FEC (Forward Error Correction), предусматривающую применение помехоустойчивых кодов для исправления ошибок. Целесообразность применения того или иного способа защиты зависит от характера и параметров ошибок в каналах. Распространенные помехоустойчивые коды ориентированы на исправление аддитивных ошибок, а не ошибок синхронизации, приводящих к возникновению вставок и выпадений бит.

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

Известные устройства таких фирм, как Anritsu, Hewlett Packard, International Data Sciences Inc., SyntheSys Research Inc., Tektronix Inc., Finisar Systems и др. позволяют получать достаточную информацию об аддитивных ошибках в различных цифровых каналах передачи информации. Однако ни в одном из известных устройств не реализованы алгоритмы вычисления параметров вставок и выпадений. Сложность создания названных алгоритмов заключается в том, что ошибки синхронизации проявляются на фоне аддитивных помех, всегда присутствующих в реальных каналах. Последние могут приводить к увеличению погрешности вычислений длин вставок (выпадении) и их локаторов. Степень влияния аддитивных помех на погрешность вычисления параметров ошибок синхронизации практически не исследована.

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

Диссертационная работа выполнена в соответствии с межвузовской научно-технической программой П.Т.614 «Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности», приказ Министерства общего и профессионального образования Российской Федерации №572 от 2.03.98 г.

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

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

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

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

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

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

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

6. Разработка алгоритмов и программ ПЭВМ для статистической обработки выходных данных УВПОС.

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

Научная новизна работы:

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

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

3. Создан алгоритм ранжирования относительных локаторов синхросимволов по частоте их появления, позволяющий на основе

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

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

Практическая ценность работы состоит в следующем:

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

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

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

- вероятность возникновения недопустимой (фатальной) погрешности определения параметров ошибок синхронизации не превышает 0,01...0,1 в диапазоне изменения вероятностей фоновых аддитивных помех [lO'^lO"6] и ошибок синхронизации в диапазоне [0,225-Ю"2,0,225-Ю'5] на бит;

- среднее значение абсолютной погрешности определения локаторов вставок и выпадений не превышает 1-3 бит в диапазоне изменения вероятностей фоновых аддитивных помех [Ю^КГ®] и ошибок синхронизации [0,225-Ю"2, 0,225-10'5] на бит.

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

Реализация и внедрение. Результаты диссертационной работы были использованы в ООО Компания ДЕМОС (г. Москва), в компании Acuvision (Великобритания) при разработке встроенного модуля измерения характеристик ошибок спутникового демодулятора по стандарту DVB-S2 (Digital Video Broadcasting - Satellite 2), внедрены в учебном процессе Курского государственного технического университета

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на Международных и Российских научно-технических конференциях: МНТК «Распознавание - 99» (г. Курск, 1999 г.); МНТК «Распознавание - 2001» (г. Курск, 2001 г.), МНТК «Распознавание - 2003» (г. Курск, 2003 г.); МНТК «Медико-экологические информационные технологии» (г. Курск, 2000 г.); РНТК «Интеллектуальные и информационные системы» (г. Тула, 2000 г.); РНТК «Новые информационные технологии» (г. Москва, 2001, 2002 гг.); МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2001 г.); на научно-технических семинарах кафедры «Вычислительная техника» Курского государственного технического университета с 1999 по 2004 гг.

Публикации. По материалам диссертации опубликовано 11 работ, в том числе 2 статьи и патент РФ.

Личный вклад автора. В работах, опубликованных в соавторстве, лично автором в [8] разработан алгоритм обнаружения вставок и выпадений бит на фоне аддитивных помех; в [1,2,4] создан метод вычисления параметров ошибок синхронизации, основанный на вычислении разности двух локаторов поразрядных символов в эталонной и принятой из канала псевдослучайных последовательностях (локаторный метод), в [3] создан алгоритм ранжирования относительных локаторов синхросимволов по частоте их появления; в [2,10] разработан корреляционный метод вычисления параметров ошибок синхронизации, в [3,5] разработаны алгоритмы и схемы устройства вычисления параметров ошибок синхронизации.

На защиту выносятся.

1. Алгоритм обнаружения вставок и выпадений бит на фоне аддитивных

помех

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

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

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и 8 приложений. Работа содержит 122 страницы текста, поясняется 44 рисунками и 16 таблицами, список литературы включает 84 наименования

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

эксплуатацию новых систем FEC, ориентированных на каналы со вставками и выпадениями бит.

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

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

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

В качестве основной характеристики ошибок в цифровых каналах используется коэффициент битовых ошибок (Bit Error Ratio или BER), выражающий относительную частоту появления ошибочно принятых бит сообщения. В реальных цифровых каналах кроме битовых (аддитивных) ошибок наблюдаются ошибки синхронизации. Современные методики измерения параметров цифрового канала предусматривают отключение режима определения параметра ошибки (BER) при потере большого массива данных, Известные методы обнаружения ошибок синхронизации позволяют ограничить влияние этих ошибок на оценки характеристик битовых ошибок.

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

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

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

В диссертации использован и развит метод обнаружения ошибок синхронизации, предложенный к.т.н. Егоровым СИ., и основанный на том, что в принятой из канала выходной битовой последовательности, образованной из поданной на вход канала эталонной тестовой последовательности, выделяются два смежных отрезка длины к бит, имеющие один общий бит. Эти отрезки будут называться соответственно правым и левым окном. В каждом окне вычисляются меры близости между отрезком принятой из канала последовательности и всеми возможными циклическими сдвигами эталонной тестовой последовательности. Затем определяется величина сдвига L, которому соответствует максимальное значение данной меры (вес). Таким образом, получаются две оценки наиболее вероятных значений фаз последовательности в каждом из окон относительно центрального бита (слева и справа и исходная задача обнаружения ошибок синхронизации разделяется на две подзадачи определения фаз в каждом из окон. Найденные оценки значений фаз позволяют определить наличие и число вставленных или выпавших бит, т.е. тип ошибки синхронизации и ее длину в битах. По разности оценок можно судить о величине вставки или выпадения

^insertion = (Lr - Li) mod T, ALdtiaton = (Li ~ Lr) mod T, где Т- период используемой тестовой псевдослучайной последовательности.

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

1. Вычислить оценки наиболее вероятных фаз и их веса для левого (Li, W0 и правого (Lr, Wr) окон.

2. Если Li = Lr, то перейти к п.7.

3. Если PrevWj < PrevWt или W] > Wr то перейти к п.7.

4. Если Wj < Threshold или Wr < Threshold, то выдать на выход "Шум" и перейти к п.7.

5. Вычислить ALmsetton = (Lr ~ Ц) mod Т И ALdeletion = (Li - Lr) mod Т.

6. Если ALinsetan < ALdelibon, TO фиксируем вставку ALmsettion бит, иначе фиксируем выпадение ALdeletmn бит.

7. Запомнить текущие веса: PrevWi = Wi, PrevWr = Wr.

8. Перейти к п. 1.

Здесь Threshold - минимально допустимое пороговое значение весов.

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

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

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

где Ь - наиболее вероятная фаза последовательности; Ж( - значение коэффициента взаимной корреляции при сдвиге эталонной

последовательности; Я/ - элементы эталонной тестовой последовательности; Ь, - элементы принятой из канала последовательности; Т - период эталонной тестовой последовательности.

Метод параллельной обработки коэффициентов взаимной корреляции

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

функционирующих счетчиках (см. рис. 1) и реализации вычислений по формуле (1) с помощью пирамидальной свертки содержимого счетчиков и их номеров.

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

синхросимволом, где т - степень порождающего многочлена последовательности; Т — 2м-1 - период М-последовательности. Индекс} будет называться локатором эталонного синхросимвола, который фактически является порядковым номером синхросимвола на одном периоде эталонной тестовой последовательности. Благодаря псевдослучайным свойствам М-последовательности имеет место однозначное взаимное соответствие локатора и синхросимвола (m-битного символа), так как выборка Т взятых

0)

(2)

1=0

подряд синхросимволов М-последовательности является перестановкой всех чисел от 1 до 2я—1.

Между локаторами и синхросимволами М-последовательности существует связь, заключающаяся в следующем. Биты М-последовательности можно определить через функцию следа, отображающую элементы поля в элементы поля 2к):

VM = I *

Для двоичной М-последовательности v=w, к=1, поэтому очередной элемент М-последовательности определяется следующим образом:

СинхросимволЛупри этом может быть выражен через базисные элементы а"... «"""'поля 2й) следующим образом:

^ = = 1 ¿'-с,, (3)

Я1—1

где j - локатор синхросимвола, * = <*•', с

Таким образом, введенный выше локатор синхросимволаj определяется как j == loga х, ах находится из следующего уравнения, составленного на основе равенства (3):

Aj = ^Г1срхгР , где Ср - некоторые константы, ср е GF(2").

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

(л > Л+1 > ■ • ■■> А+к-2 ' Л/Ш )>

где i - номев овального синхросимвола в потоке.

Локатор L(Ai) реального синхросимвола в общем случае не соответствует локатору i эталонного синхросимвола из-за сдвигов, вызываемыми вставками и выпадениями бит и искажениями кодов

фоновыми аддитивными помехами, т.е. в общем случае ¿(Л,) Ф i mod Т,

-оператор нахождения локатора синхросимвола по таблице

соответствия локаторов и синхросимволов М-последовательности.

В окне находятся локаторы синхросимволов и пересчитываются по модулю Т относительно реального локатора первого синхросимвола в

окне. Таким образом, получается следующий вектор окна:

Элементы этого вектора являются относительными локаторами R¡, представляющими собой разности реальных локаторов L(At) и значений i в счетчике по модулю Т: Е^ = Lfá)-ResTi. Относительные локаторы R¡ соответствуют величинам реальных сдвигов между синхросимволами последовательности, принятой из канала, и синхросимволами эталонной тестовой последовательности в каждой ее i-ой позиции. В качестве оценки наиболее вероятной фазы выбирается такое значение относительного локатора, которое чаще всего встречается в векторе окна. Такое значение будет называться существенным относительным локатором R.

Существенный относительный локатор может быть найден с помощью разработанного алгоритма (см. табл. 1) ранжирования элементов очереди по частоте их появления. Алгоритм для своей работы использует 4 массива: Cnt, Elem, Pos и LB. Массивы Cnt, Elem и Pos имеют размер Т, а массив LB имеет размер к+\. Алгоритм производит ранжирование элементов очереди в каждый момент времени только на основании входящего (InElem) и выходящего (Ouffilem) элементов очереди, причем обработка каждого из двух элементов является независимой. После завершения каждого цикла работы алгоритма элементы массива Elem находятся в упорядоченном состоянии. Предлагаемый алгоритм выполняется за фиксированное число шагов, не зависящее от величины Т, как при программной, так и при аппаратной реализации, что определяет его новизну.

Таблица 1

Алгоритм ранжирования элементов очереди

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

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

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

На рис. 1 приведен фрагмент функциональной схемы устройства вычисления параметров ошибок синхронизации, использующего корреляционный метод. Здесь 1,4,5 - регистры сдвига; 2,3 - генераторы эталонной псевдослучайной последовательности; WINSIZE - длина окна. Дальнейшая обработка сетью компараторов заключается в нахождении порядкового номера счетчика, содержащего максимальное значение коэффициента взаимной корреляции. Номер этого счетчика является величиной оценки фазы для данного окна.

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

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

Оценка сложности корреляционного УВПОС в основном определяется сетью компараторов и равна (4,5-2m+9,5) т+2'"+33 слайсов. Емкость требуемой памяти для корреляционного УВПОС составляет (т+1)-2тН-2-т-1 бит. Сложность локаторного УВПОС оценивается 29т+59 слайсами и 2m2+(S-2m-битами необходимой памяти соответственно. В таблице 2 приведено количество требуемых слайсов и емкость памяти разных типов

ПЛИС при реализации устройств с разными т, наиболее применимыми на практике.

1 удаагЕ

1 -1'

К сети компараторов

Рис. 1. Функциональная схема блока вычисления множества коэффициентов взаимной корреляции

Битовый поток

RG1 1

WINSIZE-1

Л

\ ЦА) /

RG2

SB

WINSIZE

Счетчик imodT

FIF01

VZ7

INLOC ENABLE OUTLOC

Блок нахождения существенного относительного локатора синхросимвола NUM RLOC

W.

ш

WINSIZE + m -2

FIF02

FIF03

LNUM LRLOC RNUMRRLOCCB Блок принятия решения о наличии ошибок SYNCERR INS/DEL DL ADDERR NOISE

SYNCERR INS/DEL DL ADDERR Блок формирования потока состояний канала WRITE ERRTYPE ERRSIZE

T Г

Строб Тип Длина Отказ от записи ошибки ошибки измерения к устройству регистрации информации об ошибках

Рис. 2. Структурная схема локаторного УВПОС

Быстродействие разработанных устройств определяется следующим. Время обработки каждого бита принятой из канала последовательности корреляционным УВПОС составляет 2 такта, а локаторным УВПОС - 22 такта. Учитывая достижимые тактовые частоты в 100-200 МГц для семейства ПЛИС ХШпх УМех-П, максимальная допустимая скорость передаваемых данных в исследуемых каналах составит приблизительно 50-100 Мбит/с для корреляционного метода и 5-10 Мбит/с для локаторного метода. Вычислительная сложность разработанных УВПОС при реализации на специализированных программируемых сигнальных микропроцессорах составит ~200+27-Г тактов для корреляционного УВПОС и ~230 тактов для локаторного УВПОС (Г= 2™-1).

Таблица 2

Верхние оценки сложности двух УВПОС для некоторых значений т,

наиболее применимых на практике

т Корреляционное УВПОС Локаторное УВПОС

Кол-во Емкость Тип Кол-во Емкость Тип

слайсов памяти, бит ПЛИС слайсов памяти, бит ПЛИС

5 833 373 ХС2У250 204 1357 ХС2У40

б 1882 883 ХС2У500 233 3228 ХС2У40

7 4260 2033 ХС2У1000 262 7471 ХС2У80

8 9581 4591 ХС2У2000 291 16966 ХС2У80

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

Таблица 3

Зависимость вероятности фатальной погрешности р/ от вероятности ошибки синхронизации на бит для корреляционного и локаторного методов при различных уровнях аддитивных ошибок ВЕЯ (КГ*5, 10*, КГ2 на бит)

РЗЕ Корреляционный метод Локаторный метод

ВЕЯ ВЕЯ

Ю'6 КГ3 10 10"6 10 3 10'2

0,225'10'5 0 0 0,001 0 0 0.006

0,225' Ю4 0,002 0,001 0,002 0,002 0,002 0,004

0,225-10° 0,013 0,012 0,012 0,013 0,013 0,012

0.224-10'' 0,104 0,093 0,099 0,104 0,104 0.100

0,215-Ю'1 0,575 0.574 0,570 0,595 0,595 0,586

В таблице 3 приведена зависимость вероятности фатальной погрешности от вероятности ошибки синхронизации на бит в канапе для

корреляционного и локаторного методов при различных уровнях аддитивных

ошибок. Анализ данной таблицы показывает, что вероятность фатальной погрешности не превышает 0,01...0,1 при вероятностях возникновения фоновых аддитивных помех не более, чем ю-2 на бит, и вставок (выпадений) бит не более, чем '0,225-10"2 на бит. На семействе графиков (рис. 3) приведена зависимость среднего значения абсолютной погрешности вычисления локаторов вставок и выпадений в битах от вероятности ошибки

синхронизации на бит р$в в канале для корреляционного и локаторного методов при различных уровнях аддитивных ошибок (10"*, Ю-3, 10 ~2 на бит). Анализ данных семейств графиков показывает, что среднее значение абсолютной погрешности определения локаторов вставок и выпадений не превышает 1-3 бит при вероятностях возникновения фоновых аддитивных помех не более, чем на бит, и вставок (выпадений) бит не более, чем на бит.

абс* бит

3 -

2,5 2 1,5

........

Ж---«п —*--

—ж-—^

——'

* "-

(BER)

r»-Loc(1,00E-6) Bit (1,00Е-6) -*-Loc(1,00E-3) -X-Bit(1,00E-3) -*-Loc(1,00E-2) Bit (1,00E-2)

1.00E-06 1.00E-05 1.00E-04 1.00E-03 1.00E-02 PsE

Рис. 3. Зависимость среднего значения абсолютной погрешности вычисления локаторов вставок и выпадений в битах Дабс от вероятности ошибки синхронизации на бит р$в для корреляционного (Bit) и локаторного методов (Loc) при различных уровнях аддитивных ошибок BER

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

распределения длин пакетов аддитивных ошибок, вставок и выпадений, безошибочных интервалов.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

2. Создан локаторный метод определения длин и позиций вставок и выпадений бит на основе вычисления разности двух локаторов синхросимволов эталонной и принятой из канала псевдослучайных последовательностей (значений относительных локаторов синхросимволов), а также алгоритм ранжирования последних по частоте их появления, позволяющие при последовательной реализации вычислительных процессов достичь быстродействия одного из вариантов разработанных устройств, достаточного для нахождения параметров ошибок синхронизации при скоростях передачи данных в исследуемых каналах до 10 Мбит/с. При этом степень требуемого увеличения тактовой частоты данного варианта устройства по отношению к тактовой частоте передачи выходной битовой последовательности исследуемого канала не превышает 22-х раз.

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

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

(неустранимой) погрешности и среднее значение абсолютной погрешности определения локаторов вставок и въшадений не превышают соответственно 0,01...0,1 и 1-3 бит при вероятностях возникновения фоновых аддитивных помех не более, чем 10 2 на бит, и вставок (выпадений) бит не более, чем

0.225.Ю"2 на бит.

5. На основании найденных оценок погрешности вычисления параметров ошибок синхронизации, затрат времени на обработку одного принятого из канала бита и аппаратной сложности реализации созданных алгоритмов могут быть рекомендованы следующие области применимости разработанных двух вариантов архитектуры устройств вычисления параметров ошибок синхронизации: при необходимости определения параметров вставок (выпадений) в реальном масштабе времени целесообразно использовать второй вариант устройства, основанный на корреляционном методе, несмотря на значительную его аппаратную сложность (833...9581 слайсов ПЛИС типов ХС2У250...ХС2У2000); при определении параметров вставок (выпадений) в низкоскоростных каналах со скоростями передачи до 10 Мбит/с целесообразно использовать первый вариант устройства, основанный на локаторном методе, так как он может быть реализован на значительно более дешевых типах ПЛИС при меньшей от 4 до 30 раз аппаратной сложности (204...291 слайсов ПЛИС типов ХС2У40... ХС2У80).

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Глухарев И.Н., Егоров СИ., Типикин А.П. Измерение характеристик ошибок в цифровых каналах передачи информации // Телекоммуникации. 2002. №8. С. 16-23.

2. Глухарев И.Н., Егоров СИ., Типикин А.П. Корреляционный и локаторный методы измерения параметров ошибок синхронизации в цифровых каналах передачи информации // Телекоммуникации. 2003. №12. С. 12-18.

3. Патент 2192038 Россия, О 06 Б 11/00, О 08 С 25/00. Устройство измерения параметров ошибок в канале / СИ. Егоров, И.Н. Глухарев, А.П. Типикин -№2001119781/09; Заявлено 16.07.2001; Опубл. 27.10.2002, Бюл. №30. 36 с.

4. Егоров СИ., Глухарев И.Н. Измерение характеристик ошибок типа вставок/выпадений бит в каналах передачи цифровой информации // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Материалы четвертой междунар. науч.-техн. конф. Курск, 1999. С. 145-147.

5. Егоров СИ., Глухарев И.Н. Устройство измерения параметров ошибок в каналах передачи и воспроизведения данных // Оптико-электронные приборы и устройства в системах распознавания обратое, обработки изображений и символьной информации: Материалы пятой междунар. науч.-техн. конф. Курск, 2001. С. 166-168.

6. Глухарев И.Н. Метод обнаружения и измерения характеристик ошибок синхронизации в каналах передачи данных // Интеллектуальные и информационные системы: Тезисы докладов региональной науч.-техн. конф. Тула: ТулГУ, 2000. С. 48-51.

7. Глухарев И.Н. Обнаружение ошибок типа вставок/выпадений бит в каналах передачи и воспроизведения данных // Новые информационные технологии: Тезисы докладов девятой междунар. студенческой школы-семинара. М.: МГИЭМ, 2001. С. 65-67.

8. Егоров СИ., Глухарев И.Н. Измерение параметров ошибок синхронизации в цифровых каналах передачи и воспроизведения информации // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Материалы междунар. науч.-техн. конф. Рязань: РГРА, 2001. С. 86-88.

9. Глухарев И.Н. Устройство измерения параметров ошибок в цифровых каналах передачи информации // Новые информационные технологии: Тезисы докладов десятой юбилейной междунар. студенческой школы-семинара. М.: МГИЭМ, 2002. С. 89-91.

10. Глухарев И.Н., Егоров СИ. Корреляционный метод измерения параметров ошибок синхронизации в каналах передачи данных // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Материалы шестой междунар. науч.-техн. конф. Курск, 2003. С. 176-178.

11. Глухарев И.Н. Имитационное моделирование корреляционного и локаторного методов измерения параметров ошибок синхронизации в каналах передачи данных // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Материалы шестой междунар. науч.-техн. конф. Курск, 2003. С. 173-175.

Соискатель

ИД №06430 от 10.12.01 Подписано в печать Формат 60x84 1/16. Печать офсетная.

Печ. л. 1,0. Тираж 100 экз Заказ ¿ДО. Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета 305040, Курск, ул. 50 лет Октября, 94.

№25038

Введение.

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

1.1 Основные характеристики ошибок в цифровых каналах.

1.2 Методы определения характеристик ошибок.

1.2.1 Определение коэффициента битовых ошибок.

1.2.2 Известные методы обнаружения ошибок синхронизации.

1.3 Устройства вычисления характеристик аддитивных ошибок.

1.4 Актуальность задачи создания методов и устройств вычисления параметров ошибок синхронизации (УВПОС) на фоне аддитивных помех

1.5 Выводы.

2 Методы и аппаратно-ориентированные алгоритмы определения параметров ошибок синхронизации в каналах со вставками и выпадениями бит.

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

2.2 Корреляционный метод определения параметров ошибок синхронизации.

2.3 Локаторный метод определения параметров ошибок синхронизации на основе синхропоследовательности с особыми свойствами.

2.4 Алгоритм ранжирования относительных локаторов синхросимволов по частоте их появления.

2.5 Предварительное исследование разрешающей способности корреляционного и локаторного методов.

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

2.7 Алгоритмы оперативной статистической обработки выходных данных УВПОС.

2.8 Выводы.

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

3.1 Структурная и функциональная организация УВПОС.

3.1.1 УВПОС на основе корреляционного метода.

3.1.2 УВПОС на основе локаторного метода.

3.2 Блок нахождения существенного относительного локатора синхросимвола.

3.3 Блок принятия решения о наличии ошибок.

3.4 Блок формирования потока состояний канала.

3.5 Блок формирования входного битового потока.

3.6 Оценки сложности и быстродействия корреляционного и локаторного УВПОС.

3.7 Выводы.

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

4.1 Организация программной модели.

4.1.1 Принципы моделирования источника ошибок и алгоритмов функционирования УВПОС.

4.1.2 Структурная схема модели для исследования алгоритмов УВПОС

4.2 Методика определения параметров и характеристик ошибок синхронизации на модели.

4.3 Результаты проверки погрешности вычисления параметров ошибок синхронизации на выходе УВПОС.

4.4 Результаты проверки погрешности оценки вероятностных характеристик ошибок синхронизации.

4.5 Выводы.

Актуальность работы. В современном обществе все большее значение приобретают сети ЭВМ. Их надежность и производительность во многом определяется качеством цифровых каналов, используемых в первичных сетях, а также качеством каналов воспроизведения данных во внешних запоминающих устройствах (ВЗУ) [1-12].

Качество цифрового канала определяется скоростью передачи данных и характеристиками ошибок в канале [13-20]. Знание характеристик ошибок в каналах требуется при разработке и вводе в эксплуатацию контроллеров ВЗУ и аппаратуры передачи данных сетей ЭВМ, содержащих в своем составе систему FEC (Forward Error Correction), предусматривающую применение помехоустойчивых кодов для исправления ошибок. Целесообразность применения того или иного способа защиты зависит от характера и параметров ошибок в каналах. Распространенные помехоустойчивые коды ориентированы на исправление аддитивных ошибок, а не ошибок синхронизации, приводящих к возникновению вставок и выпадений бит [21-24].

Ошибки синхронизации возникают на выходах демодуляторов в трактах воспроизведения внешних запоминающих устройств ЭВМ и модемах каналов связи сетей ЭВМ [25-34]. Они проявляются в виде вставок и выпадений бит в демодулированной двоичной информационной последовательности, приводят к ее сдвигам и образованию протяженных пакетов ошибок, превышающих корректирующую способность самых мощных помехоустойчивых кодов [13]. Для оценки качества работы канала и проектирования устройства, исправляющего ошибки синхронизации, необходимо знание диапазона изменения их параметров: длин вставок (выпадений) и их локаторов (позиций) в считываемом секторе или передаваемом пакете данных. Названные параметры ошибок синхронизации могут быть найдены в результате статистических исследований каналов с помощью быстродействующих специализированных вычислительных устройств, работающих в реальном масштабе времени на тактовой частоте демодулированной последовательности. Специализированное устройство должно обнаруживать появление вставок (выпадений), точно вычислять их длины и локализовывать их местоположение.

Известные устройства таких фирм, как Anritsu, Hewlett Packard, International Data Sciences Inc., SyntheSys Research Inc., Tektronix Inc., Finisar Systems и др. позволяют получать достаточную информацию об аддитивных ошибках в различных цифровых каналах передачи информации. Однако ни в одном из известных устройств не реализованы алгоритмы вычисления параметров вставок и выпадений. Сложность создания названных алгоритмов заключается в том, что ошибки синхронизации проявляются на фоне аддитивных помех, всегда присутствующих в реальных каналах. Последние могут приводить к увеличению погрешности вычислений длин вставок (выпадений) и их локаторов. Степень влияния аддитивных помех на погрешность вычисления параметров ошибок синхронизации практически не исследована.

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

Диссертационная работа выполнена в соответствии с межвузовской научно-технической программой П.Т.614 «Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности», приказ Министерства общего и профессионального образования Российской Федерации №572 от 2.03.98 г.

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

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

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

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

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

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

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

6. Разработка алгоритмов и программ ПЭВМ для статистической обработки выходных данных УВПОС.

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

Научная новизна работы:

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

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

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

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

Практическая ценность работы состоит в следующем:

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

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

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

- вероятность возникновения недопустимой (фатальной) погрешности определения параметров ошибок синхронизации не превышает 0,01.0,1 в диапазоне изменения вероятностей фоновых аддитивных помех [10"2,10"6] и ошибок синхронизации в диапазоне [0,225-10"2, 0,225-10"5] на бит;

- среднее значение абсолютной погрешности определения локаторов вставок и выпадений не превышает 1-3 бит в диапазоне изменения

О /Г вероятностей фоновых аддитивных помех [10" ,10' ] и ошибок синхронизации [0,225-Ю"2, 0,225-Ю"5] на бит.

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

Реализация и внедрение. Результаты диссертационной работы были использованы в ООО Компания ДЕМОС (г. Москва), в компании Acuvision (Великобритания) при разработке встроенного модуля измерения характеристик ошибок спутникового демодулятора по стандарту DVB-S2 (Digital Video Broadcasting - Satellite 2), внедрены в учебном процессе Курского государственного технического университета.

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на Международных и Российских научно-технических конференциях: МНТК «Распознавание - 99» (г. Курск, 1999 г.); МНТК «Распознавание - 2001» (г. Курск, 2001 г.); МНТК «Распознавание - 2003» (г. Курск, 2003 г.); МНТК «Медико-экологические информационные технологии» (г. Курск, 2000 г.); РНТК «Интеллектуальные и информационные системы» (г. Тула, 2000 г.); РНТК «Новые информационные технологии» (г. Москва, 2001, 2002 гг.); МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» (г. Рязань, 2001 г.); на научно-технических семинарах кафедры «Вычислительная техника» Курского государственного технического университета с 1999 по 2004 гг.

Публикации. По материалам диссертации опубликовано 11 работ, в том числе 2 статьи и патент РФ.

Личный вклад автора. В работах, опубликованных в соавторстве, лично автором в [48] разработан алгоритм обнаружения вставок и выпадений бит на фоне аддитивных помех; в [46,50,55] создан метод вычисления параметров ошибок синхронизации, основанный на вычислении разности двух локаторов w-разрядных символов в эталонной и принятой из канала псевдослучайных последовательностях (локаторный метод); в [54,63] создан алгоритм ранжирования относительных локаторов синхросимволов по частоте их появления; в [55,56] разработан корреляционный метод вычисления параметров ошибок синхронизации, в [52,54] разработаны алгоритмы и схемы устройства вычисления параметров ошибок синхронизации.

На защиту выносятся:

1. Алгоритм обнаружения вставок и выпадений бит на фоне аддитивных помех.

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

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

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и 8 приложений. Работа содержит 122 страницы текста, поясняется 44 рисунками и 16 таблицами; список литературы включает 84 наименования.

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

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

2. Создан локаторный метод определения длин и позиций вставок и выпадений бит на основе вычисления разности двух локаторов синхросимволов эталонной и принятой из канала псевдослучайных последовательностей (значений относительных локаторов синхросимволов), а также алгоритм ранжирования последних по частоте их появления, позволяющие при последовательной реализации вычислительных процессов достичь быстродействия одного из вариантов разработанных устройств, достаточного для нахождения параметров ошибок синхронизации при скоростях передачи данных в исследуемых каналах до 10 Мбит/с. При этом степень требуемого увеличения тактовой частоты данного варианта устройства по отношению к тактовой частоте передачи выходной битовой последовательности исследуемого канала не превышает 22-х раз.

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

4. На основании разработанной методики многопараметрических статистических исследований стабильности и погрешности определения параметров ошибок синхронизации, использованной при имитационном моделировании названных алгоритмов и устройств, установлены следующие рабочие диапазоны их применимости: вероятность возникновения фатальной (неустранимой) погрешности и среднее значение абсолютной погрешности определения локаторов вставок и выпадений не превышают соответственно 0,01.0,1 и 1-3 бит при вероятностях возникновения фоновых аддитивных помех не более, чем

2 -2 10" на бит, и вставок (выпадений) бит не более, чем 0,225-10 на бит.

5. На основании найденных оценок погрешности вычисления параметров ошибок синхронизации, затрат времени на обработку одного принятого из канала бита и аппаратной сложности реализации созданных алгоритмов могут быть рекомендованы следующие области применимости разработанных двух вариантов архитектуры устройств вычисления параметров ошибок синхронизации: при необходимости определения параметров вставок (выпадений) в реальном масштабе времени целесообразно использовать второй вариант устройства, основанный на корреляционном методе, несмотря на значительную его аппаратную сложность (833.9581 слайсов ПЛИС типов XC2V250.XC2V2000); при определении параметров вставок (выпадений) в низкоскоростных каналах со скоростями передачи до 10 Мбит/с целесообразно использовать первый вариант устройства, основанный на локаторном методе, так как он может быть реализован на значительно более дешевых типах ПЛИС при меньшей от 4 до 30 раз аппаратной сложности (204.291 слайсов ПЛИС типов XC2V40.XC2V80).

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

Заключение

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

1. Прокис Джон. Цифровая связь. Пер. с англ. / Под ред. Д.Д. Кловского. -М.: Радио и связь. 2000. 800 с.

2. Никамин В.А. Форматы цифровой звукозаписи. Санкт-Петербург: Издательство ЗАО «Элби», 1998 г. - 264 с.

3. Передача дискретных сообщений / Под ред. Шувалова.-М.:Радио и связь, 1990.-464 с.

4. Боккер П. Передача данных: Техника связи в системах телеобработки данных. В 2-х томах. Том 2. Устройства и системы: Пер. с нем./ Под ред. Д. Д. Кловского. М.: Радио и связь, 1981. - 256 с.

5. Типикин А.П., Петров В.В., Бабанин А.Г. Коррекция ошибок в оптических накопителях информации. Киев: Наукова думка, 1990. -172 с.

6. Иванов А.Б. Волоконная оптика: компоненты, системы передачи, измерения. М.: Компания САЙРУС СИСТЕМС, 1999 г., 672 е., ил.

7. Назаров А.Н., Симонов М.В. ATM: Технологии высокоскоростных сетей. М.: Эко-Трендз, 1997.

8. Тихонов Д.В. Передача факсимильных сообщений в цифровых системах связи со статистическим уплотнением // Телекоммуникации. 2003. №8. С. 15-19.

9. Tri Т. На. Digital Satellite Communications. McGraw-Hill Publishing Company. 1990.

10. Ю.Шляпоберский В.И. Основы техники передачи дискретных сообщений. М.: Связь, 1973.480 с.

11. П.Левин Л.С., Плоткин М.А. Основы построения цифровых систем передачи. М.: Связь, 1975, 176 с.

12. David R. Smith. Digital Transmission Systems, Second Edition, Charman & Hall, 1993.

13. Бакланов И.Г. Технологии измерений первичной сети. Часть 2. Системы синхронизации, B-ISDN, ATM. М.: Эко-Трендз, 2000.

14. Коричнев Л.П., Королев В.Д. Статистический контроль каналов связи. -М.: Радио и связь, 1989. 240 с.

15. Бакланов И.Г. ISDN и FRAME RELAY: Технология и практика измерений. -М.: Эко-Трендз, 1998.

16. Бакланов И.Г. Измерительно-контрольные системы технология измерений XXI века // Телевестник, №3, 1997.

17. П.Бакланов И.Г. Технологии измерений в современных телекоммуникациях. -М.: Эко-Трендз, 1997.

18. Peyton Z. Peebles, Jr. Digital Communication Systems. Prentice-Hall, Inc. 1987.

19. Roger L. Freeman. Fundamentals of Telecommunications. Published by John Wiley & Sons, Inc. 1999.

20. Захаров И.С., Атакищев О.И., Сайбель А.Г. Основные показатели результативности процесса функционирования измерительных систем с переменными параметрами элементов // Телекоммуникации. 2003. №7. С. 2-5.

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

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

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

24. Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование. Ростов н/Д, 2002. - 288 с.

25. Дж. Дж. Стиффлер. Теория синхронной связи. Пер. с англ. Б.С. Цыбакова под ред. Э.М. Габидулина. -М.: Связь, 1975- 488 с.

26. Колтунов Н.Н., Коновалов В.Г., Лангуров З.И. Синхронизация по циклам в цифровых системах связи. М.:Связь, 1980.-151 с.

27. Рекомендации по метрологическому обеспечению системы тактовой синхронизации (ТСС) на цифровой сети общего пользования Российской Федерации. ЦНИИС, 1998.

28. John С. Bellamy. Digital Network Synchronization / IEEE Communications Magazine, vol. 33, No. 4, April, 1995.

29. David L. Mills. Internet Time Synchronization: The Network Time Protocol, IEEE Transactions on Communications, vol. 39, No. 10, October, 1991.

30. American National Standard for Telecommunications. «Synchronization Interface Standards for Digital Networks». ANSI Tl. 101 1994.

31. Abate J. E., et al. AT&T's New Approach to the Syncronizatoin of Telecommunication Networks. IEEE Communications Magazine, vol. 27, No. 4, April, 1989.

32. Атакищев О.И., Куликов JI.C., Мусакин Е.Ю. Алгоритм распознавания синхронной цифровой иерархии // Телекоммуникации. 2003. №2. С. 2-4.

33. Линдсей В. Системы синхронизации в связи и управлении. Нью-Джерси, 1972. Пер. с англ. Под ред. Ю.Н.Бакаева и М.В. Капранова, М., «Сов. радио», 1978, 600 с.

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

35. ITU Recommendation G.821 // Error performance of an international digital connection operating at a bit rate below the primary rate and forming part of an integrated services digital network ITU-T. (www.itu.org).

36. ITU Recommendation G.826 // Error performance parameters and objectives for international, constant bit rate digital paths at or above the primary rate. ITU-T. (www.itu.org).

37. ITU Recommendation G.822 // Controlled slip rate objectives on an international digital connection. ITU-T. (www.itu.org).

38. Jim Waschura. C213: Bit error analysis and beyond. Communication, design, engineering conference. (http://www.svnthesYsresearch.com/support/wp/beyond.pdf).

39. McElice RJ. Finite fields for computer scientists and engineers. Boston, Kluwer Academic Publishers, 1987.

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

41. Патент № 4158193 США. МПК G08C 025/00; H04L 017/00. Data transmission test set with synchronization detector. / D'Antonio Renato A. -заявлено 06.06.77; N803987; опубл. 12.06.79.

42. Патент № 5282211 США. МПК G06F 11/00. Slip detection during bit-error-rate measurement. I Robert M. Manlick, Matthew L. Fitchtenbaum -заявлено 15.10.91 N776850; опубл. 25.01.94.

43. Патент № 5392289 США. МПК G06F 11/00; H04L 12/00; H04L 7/00; Н03М 13/00. Error rate measurement using a comparison of received and reconstructed PN sequences. / George R. Varian, Palo Alto, Calif заявлено 13.10.93; N136075; опубл. 21.02.95.

44. Патент № 5349611 США. МПК H04L 007/00; H04L 009/00; H04J 003/6. Recovering synchronization in a data stream. / George R. Varian, Palo Alto, Calif- заявлено 13.01.93; N003896; опубл. 20.09.95.

45. Егоров С.И., Глухарев И.Н. Измерение характеристик ошибок типа вставок/выпадений бит в каналах передачи цифровой информации // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации:

46. Материалы четвертой междунар. науч.-техн. конф. Курск, 1999. С. 145147.

47. Глухарев И.Н. Метод обнаружения и измерения характеристик ошибок синхронизации в каналах передачи данных // Интеллектуальные и информационные системы: Тезисы докладов региональной науч.-техн. конф. Тула: ТулГУ, 2000. С. 48-51.

48. Глухарев И.Н. Обнаружение ошибок типа вставок/выпадений бит в каналах передачи и воспроизведения данных // Новые информационные технологии: Тезисы докладов девятой междунар. студенческой школы-семинара. М.: МГИЭМ, 2001. С. 65-67.

49. Глухарев И.Н., Егоров С.И., Типикин А.П. Измерение характеристик ошибок в цифровых каналах передачи информации // Телекоммуникации. 2002. №8. С. 16-23.

50. Егоров С.И., Глухарев И.Н. Алгоритм обнаружения и измерения характеристик ошибок синхронизации в каналах передачи данных // Медико-экологические информационные технологии: Материалы междунар. науч.-техн. конф. Курск, 2000. С. 136-139.

51. Глухарев И.Н. Устройство измерения параметров ошибок в цифровых каналах передачи информации // Новые информационные технологии:

52. Тезисы докладов десятой юбилейной между нар. студенческой школы-семинара. М.: МГИЭМ, 2002. С. 89-91.

53. Патент 2192038 Россия, G 06 F 11/00, G 08 С 25/00. Устройство измерения параметров ошибок в канале / С.И. Егоров, И.Н. Глухарев, А.П. Типикин №2001119781/09; Заявлено 16.07.2001; Опубл. 27.10.2002, Бюл. №30. 36 с.

54. Глухарев И.Н., Егоров С.И., Типикин А.П. Корреляционный и локаторный методы измерения параметров ошибок синхронизации в цифровых каналах передачи информации // Телекоммуникации. 2003. №12. С. 12-18.

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

56. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях./ Под ред. В.Ф.Шаньгина. -М.: Радио и связь, 1999.-328 с.

57. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.: КУДИЦ-ОБРАЗ, 2001 368 с.

58. Aghes H. Chan, Richard A. Games. On the Quadratic Spans of de Bruijn Sequences. IEEE Transactions On Information Theory, vol. 36, No. 4, July 1990.-p. 822-829.

59. Gregory L. Mayhew, Solomon W. Golomb. Linear Spans of Modified de Bruijn Sequences. IEEE Transactions On Information Theory, vol. 36, No. 5, September 1990. p. 1166-1167.

60. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. : Уч. пос. М.: Издательский дом «Вильяме», 2000. -720 с.

61. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ. : Уч. пос. М.: Издательский дом «Вильяме», 2000. -832 с.

62. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. 960 с.

63. Ахо А., Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов: Пер. с англ. / Под ред. Ю.В.Матиясевича. М.: Мир, 1979.-536 с.

64. Вентцель Е.С. Теория вероятностей. М.: Наука, 1969. 576 с.

65. Феллер В. Введение в теорию вероятностей и ее приложения: Пер. с англ. / Под ред. Е.Б. Дынкина. М.: Мир, 1984. - Т.1. - 337 с.

66. Угрюмов Е.П. Цифровая схемотехника. СПб.: БХВ-Петербург, 2000. -528 с.

67. Standard ECMA-130. Data interchange on read-only 120 mm optical data disks(CD-ROM). 2nd Edition June 1996. http://www.ecma-international.org/publications/files/ecma-st/ECMA-130.pdf

68. Суворова E.A., Шейнин Ю.Е. Проектирование цифровых систем на VHDL. СПб.: БХВ-Петербург, 2003. - 576 с.

69. Бибило П.Н. Основы языка VHDL. М.: СОЛОН-Р, 2000. - 208 е.: ил.

70. Бибило П.Н. Синтез логических схем с использованием языка VHDL. -М.: СОЛОН-Р, 2002. 384 с.

71. Parnell К., Mentha N. Programmable Logic Design Quick Hand Book. Xilinx Corp., 2002, 201 p.

72. Virtex-II Pro Platform FPGA Handbook Xilinx Corp., 2002, 437 p.

73. ГОСТ P 50754-95. Язык описания аппаратуры цифровых систем VHDL. Описание языка.

74. Блох Э.Л. и др. Модели источника ошибок в каналах передачи цифровой информации. М., «Связь», 1971. - 312 с.

75. Patrick А.Н. Bours. Codes for Correcting Insertion and Deletion Errors. PhD thesis, Eindhoven Technical University, June 1994.

76. Edward A. Ratzer, David J.C. MacKay. Codes for Channels with Insertions, Deletions and Substitutions. 2nd International Symposium on Turbo Codes and Related Topics, Brest, France, 4-7 September 2000.

77. David Leigh. Capacity of Insertion and Deletion Channels. July 23, 2001.

78. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ. : Уч. пос. М.: Издательский дом «Вильяме», 2000. - 832 с.

79. КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ1. На правах рукописи1. ГЛУХАРЕВ ИГОРЬ НИКОЛАЕВИЧ

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

81. Л 3.05 Элементы и устройства вычислительной техникии систем управления