автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Имитационное моделирование процесса передачи информации по дискретным каналам связи вычислительных сетей

+ М п п

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

Моторный Евгений Николаевич

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

Специальность 05.13ЛЯ - Вычислительные машины, комплексы,

системы и сети.

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

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

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

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

доктор технических наук профессор Смирнов A.C.

Официальные оппоненты: '

• доктор технических наук ст.науч.сотр. Сидоров Ю.Е. кандидат технических наук доцент Алмазова B.C.

Ведущая организация указана в решении специализированного совета.

Защита диссертации состоится "2{г" 1992 г.

в 16 часов на заседании специализированного совета Д 063.38.04 Санкт-Петербургского государственного технического университета по адресу: 195251, Санкт-Петербург, ул.Политехническая, 29.

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

Автореферат разослан " 1992 г.

Ученый секретарь специализированного совета

К.П.Дурандин

БИиП'лО ¡е-;-'-

I. ОБЩ/Л ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Для достижения поставленной цели необходимо решить следу-

ющие основные задачи:

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

- провести анализ и выбор методов повышения временной еффективпости имитационного моделирования СПДИ и разработать соответствующее программное обеспечение;

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

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

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

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

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

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

■1. 11]к;дложеп способ ускоренного отчисления малых вероят-

ностей передачи кадра с необнаруженной ошибкой.

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

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

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

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

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

5. Составлены таблицы сложности алгоритмов быстрого преобразования Фурье в полях Галуа «р(гг )...ар(г12>, позволяющие выбрать длину и алфавит кодов Рида-Соломона или Боуза -

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

Реализация результатов работы. Теоретические и практические результаты диссертационной работы использованы в хоздоговорной НИР "Байкал", выполненной на кафедре автоматики и' вычислительной техники (ПГГТУ в 1989-1990 гг. (договор Я801805 от 29.I2.B8r).

Апробация работы и публикации. Основные положения диссертации докладывались на VII Всесоюзной научо-технической конференции "Проблемы комплексной автоматизации судовых технических средств", г. Ленинград, 1989 г. и на семинаре в НПО "Нептун" в 1990 г.

По материалам диссертации опубликовано 7 печатных работ.

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

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

Но введении обосповэна актуальность теш диссертационной работы, сформулирован.-) со цель, приведены основные научные и практические результаты," апробация и структура диссертации. ,

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

выбор метода обеспечения заданных характеристик помеха-

- о -

устойчивости и эффективности С11ДИ определяется как уровнем помех в канале связи, так и сиоциальшми требованиями к системе связи. Упростить решение задачи выбора можно, применяя метод декомпозиции - иерархическое разделение исходной задачи на ряд подзадач, допускающих независимое решение. Такое разбиение приводит к более простым математическим моделям процессов, появляется возможность применить аналитические.методы для некоторых подзадач, й работе используется декомпозиция на следующие подзадачи: ■

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

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

3. по характеристикам потоков сбойных кадров информации вычисляются характеристики уровня звена передачи данных СПДИ в применением обратной связи;

4. определяются временные характеристики для кодеров, .декодеров и средств реализации протокола функционирования

ИЩИ. '

Такая декомпозиция исходной задачи соответствует конструктивно-логической структуре СГЩИ и существующим методам расчетов. Диссертационная работа посвящена решению второй и четвертой подзадач.

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

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

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

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

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

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

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

2. Принятые ограничения дают возможность отказаться- от формирования при моделировании потока "передаваемых" данных, что позволяет: исключить формирование потока "передаваемых" данных и кодирование, применить эффективное интервальное представление потока ошибок.

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

.лее универсальные фильтры, реализующие подсчет числа ошибок или пакетов ошибок в "принятом" блоке.

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

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

запятой. Используемая в генераторе кусочно линейная аппроксимация логарифмической функции, обеспечивает результирующую точность 0,01%.

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

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

Для декодирования линейных кодов наиболее аффективными являются алгоритмы синдромного декодирования. В работе исследуются две группы таких алгоритмов: комбинаторные и табличные.

К первой группе относится предлагаемый метод весового синдромнсго декодирования, основанный на следующем алгоритме:' .1. вычисляется синдром принятого вектора §=у-Нт, где' Н - проверочная матрица кода; 2.. для всех исправляемых декодером векторов ошибок ё вычисляется вес ращюсти .синдрома е принятого вектора и синдром;) в ^ё-Н* проверяемого вектора ошибок:

wfi=w (s-se) 3. если вшолняется условие w^l, где 1 - число ошибок в проверяемом векторе, то вектор ошибок найден, производится исправление и декодирование заканчивается, иначе для следующего вектора ошибок выполняем нп-2 и 3. Для ускорения декодирования в работе предлагается вести перебор векторов ошибок от более вероятных в используемом канале передачи к менее вероятным или, при исправлении ошибок кратности более едушт, использовать при вычислении we частичные синдромы ошибок меньшей кратности. Комбинаторные методы отличаются относительно большим временем декодирования, однако требуют минимальный объем памяти для своей работы.

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

вектор синдрома

m бит n-k-m бИТ

индекс-

индекс--.

0-

ypoFieHL I

•синдром ошибка

уровень 2

Рис.Т Двухуровневая организия таблиц декодирования.

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

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

В кодеках кодов Ида-Соломона и Боуза-Чоудхури-Хоквингема используется дискретное преобразование Фурье, от эффективности реализации которого зависят временные параметры кодека. Составленные таблицы сложности алгоритмов быстрого преобразования Фурье в полях Галуа СТ(2Р)...СР(212) позволяют выбрать длину и алфавит кода в рамках ограничений задачи, имеющие минимальное время преобразования. .Тестирование разработанных программ быстрого преобразования Фурье подтверждает состоятельность оценок в приводимых таблицах.

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

Сформулированы требования к программным декодерам, позволяющие использовать их для паралельного декодирования нескольких векторов. Такой способ особенно эффективен в случае применения регулярного посимвольного перемекопия кодовых векторов, так как уменьшает время обработки одного вектора в ш раз, где я) - число переметаемых векторов. Кода-перемещения .широко использются"й-каналах с сильным пакетированием ошибок. Реализованы декодеры кодо1}-пе реме нений циклических кодов (на базе декодера Меггитв и декодера с_ вылавливанием ошибок) и - - еверточннх кодов Ивадаре.

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

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

1. Методом моделирования определяется вероятность р^ приема блока с числом ошибок большим, чем 6-1-г,.где б - минимальное расстояние кода, I - максимальное число исправляемых декодером ошибок.

2. Вычисляется оценка вероятности с необнаруживаемой ошибкой по формуле ре р^- где с* - число сочетаний из.п по ¡, с) - алфавит символов кода.

Выражение для рр получено в предположении, что синдром принятого вектора, является случайным числом, если число ошибок в (юм более (1-1-1. Числитель есть число различных синдромом , соответствующих векторчм с. исправляемой ошибкой, то есть тем, к'хгорыо будут неверно "поправлены" декодером. Знаменатель • общее число попможшх векторов синдрома. Таким образом,

G. Разработан метод весового синдромного декодирования линейных блоковых кодов. Проведено исследование характеристик декодера на его основе и сравнение с декодерам, построенными по другим алгоритмам. Результаты исследований показали, что разработанный декодер обладает удовлетворительным быстродействием при минимальных требованиях к памяти и может с успехом использоваться для работы с короткими кодами (п«Й2).

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

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

9. Составлены таблицы для оценки сложности и эффективности программной реализации быстрого преобразования Фурье в полях Галуа of(22)...GF(2,e). Таблицы позволяют выбрать алфавит и длину кодов Рида-Соломона, обеспечивающие наименьшее время работы кодеков, реализующих кодирование в частотной области.

ПУВЛЩЛЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Смирнов A.C., Моторный E.H. Модифицированный метод синдром-ного декодирования.двоичных. блоковых кодов / Ленингр.политехи, ин-т.: Л.,1989. 7с. Деп. в ВИНИТИ 28.2. 89, «386-1389.

2. Смирнов AIC., Моторный H.H. Программная реализация методов

синдромного декодирования линейных кодов/ Ленингр.политехи.ин-т.: Л., 1989. 9с. Деп. в ВИМТИ 21.3.89, JH749-B89.

3. Система расчета характеристик помехоустойчивости передачи информации по дискретному каналу связи. Моторный E.H. / Инф. листок * 508-91. Серия Р 50.50.00. Ленингр. центр научно-технической информации, 1991.

4. Моторный E.H., Смирнов A.C. Программная реализация декодеров в судовых.системах управления и контроля/ Тез. докл. к vii Всесоюзн. науч.-техн. конференции Проблемы комплексной автоматизации судовых технических средств. Л.,1989. с.214-215.

5. Моторный E.H., Смирнов A.C.- Оценки эффективности программной реализации быстрого преобразования Фурье в конечных полях gf12 >// Сб.ЛОП ВН'ГО им.акад.А.Н.Крылова. 1989. Вып.19.' С.21-25.

6. Моторный E.H. Сравнительные оценки эффективности программной реализации декодеров для кодов Рида-Соломона// Вычислительная техника, автоматика и радиоэлектроника: Сборник научных трудов.-Л. :ЛГТ.У, 1990.-с,55-59.

7.. Моторный E.H. Ймитацдашюе моделирование процесса передачи информации по дискретному каналу связи// Вычислительная техника, автоматика и радиоэлектроника: Сборник научных трудов.-Л.:ЛГТУ,T99I.

Г—

Подпжянр к .печати '''»// 9S, Лика

Тираж 100 экз. Бесплатно

Отпечатано h;i |х>т;нгринтс СИбГГ.У ¡'.¡'.¡'/.hl, Сянкт-Петербург, Политехническая ул., 29