автореферат диссертации по радиотехнике и связи, 05.12.17, диссертация на тему:Быстрое синдромное декодирование линейных блоковых кодов

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

УДК 621.391

СИТКЕВИЧ Татьяна Анатольевна

БЫСТРОЕ СШЩРОМНОЕ ДЕКОДИРОВАНИЕ ЛИНЕР.НЫХ БЛОКОВЫХ КОДОВ

Специальность 05.12.17,-Радкотехническке а телевизионные системы и устройства

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

' #

Минск, 1998

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

Научный руководитель - кандидат технических наук СЮРИН В.Н. Официальные оппоненты:

доктор технических наук, профессор Р.Х.САДЫХОВ; кандидат технических наук, доцент В.П.СУПРУН.

Оппонирующая организация - КПО «Агат»

Защита состоится «/* » МЛ^я-а. 1953 г. в /£.££, на заседавши совета по за» щите диссертаций Д. 02.15.02 в Белорусском государственном университете информатики к радиоэлектроники ш> адресу: 22002?, г. Минск, ул. П.Бропки, 6.

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

Автореферат разослан (¡-¿А- _5993 г.

Ученый секретарь совета по защите диссертаций, к.т.н.

С.Б.САЛОМАТИН

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

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

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

Связь работы с крупными научными программами, темами. Выполнение представленной работы проводилось в рамках научно-исследовательской темы "Разработка элементов информационных технологий" (№ ГР 19961190), включенной в план государственной научно-технической программы "Электроника" на 1997 г. по теме "Разработка и исследование новых принципов создания перспективных опто- и микроэлектронных систем хранения, передачи, и обработки информации", ведущая организация — Институт электроники АН РБ.

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

Для этого необходимо решить задачи: во-первых, новой организации вычислительных процессов, необходимых для реализации режима исправления ошибок; во-вторых, схемной реализации процессов кодирования и декодирования на основе использования современной элементной базы широкого назначения в виде СБИС с регулярной структурой, таких как ПЗУ, tIJIM или систолических параллельных структур (БМК, FPGA (Flash Programmable Gate Arrays)).

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

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

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

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

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

Использование полученных однозначных соотношений "конфигурация ошибок — синдром" позволяет синтезировать декодер в виде структуры ВС-ПЛМ, где последняя реализует данные соотношения, предварительно приведенные к СДНФ.

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

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

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

флагом п протоколе V.42 и заголовком в пакете ATM это является важным шагом вперед в технике помехоустойчивого кодирования.

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

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

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

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

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

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

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

Изготозлен действующий макет кодирующего устройства параллельного типа для кода БЧХ А15.7 на основе разработанного быстрого алгоритма кодирования, используемый в учебном процессе. Его испытания подтвердили увеличение скорости работы на порядок по сравнению с кодером последовательного типа.

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

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

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

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

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

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

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

■ Предложенные алгоритмы вычислений, совокупностей операций и конкретных технических приемов в процессе проектирования кодеков предоставляют возможность их реализации на элементной базе широкого назначения в виде СБИС с регулярной структурой, что позволяет снизить ее стоимость в 4-5 раз по сравнению с заказными БИС.

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

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

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

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

Апробация результатов диссертации. Результаты исследований, включенные в диссертацию, докладывались и обсуждались на: Третьем Межреспубликанском семинаре "Физика быстропротекающих плазменных процессов", проходившем в г. Гродно 11-14 мая 1992 г.; Международной научно-технической конференции "Современные средства связи", проводимой БГУИР в г.п. Нарочь в октябре 1995 г.; научно-технической конференции "Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления", проходившей в БГУ 18-22 декабря 1995 г.; республиканском научно-техническом семинаре "Организация и технология средств связи, проводившемся на базе Высшего колледжа связи в г.Минске 27 июня 1996 г.; Второй Международной конференции "Новые информационные технологии в образовании" (г. Минск, БГЭУ, 12-13 ноября 1996 г.); Второй Межпународной научно-технической конференции «Современные средства связи», проводимой БГУИР и Высшим колледжем связи в т.п. Нарочь 22-26 сентября 1997 г.

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

Структура и объем диссертации. Диссертационная работа состоит из введения, общей характеристики, четырех глав, еыводов, списка литературы из 83 наименований на б стр., 4-х приложений на 26 стр.; включает 22 иллюстрации на 8 стр., 4 таблицы кэ 2 стр.

Общий объем диссертации составляет 131 страницу. Список литературы дан в порядке следования ссылок по тексту.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

Л = *rC. i = (1)

где xi = (хI, XI.....xj- информационный вектор;

У/ = £У/. уз.....Ун) - кодовый вектор;

G - порождающая матрица кода.

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

угНт=*(у,+ еЩт =yjf + (2)

где et = (ei, ei,.... ej - вектор ошибок; Н - проверочная матрица кода.

Тогда yiHT 0 с учетом того, что G Нт = 0, и Нт=S,, где St = (Si, Si,.... Sr) - синдром, взаимно однозначно определяемый вектором ошибок, т.е. выполняется жесткое соответствие Si -> е^.

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

Далее рассмотрены основные известные методы кодирования, реализуемые в соответствии с (1), но описываемые в традиционной полиномиальной форме.

Первый метод осуществляется путем деления на порождающий полином кода g(x):

П*)*' Г1

—— = G{x) + —~, (3)

где f(x) - информационная комбинация, представленная в виде формального полинома; G(x) - целая часть от результата деления; R(x) - остаток.

Преобразуя (3), запишем:

C(x)g(x) =f(x)x't R(x). (4)

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

Суть второго метода заключается в умножении информационного полинома f(x) па порождающий полином g(x), т,e.f(x)-g(x). Ясно, что это произведение также является комбинацией циклического кода.

Третий метод предполагает использование проверочного полинома h(x), определяемого как

h(x) = (х" + JJ/gfx). (5)

в соответствии с

р(х) = Дх)хг +£((6)

i-0 О /

где ф(х) - полиномиальное представление кодового блока.

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

Известен также метод кодирования, заключающийся в суммировании записанных в ПЗУ строк матрицы О в зависимости от значений двоичных информационных символов.

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

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

min dist (у,-yi), i = 1,2к. (7)

В основе мажоритарного декодирования лежит формирование ряда контрольных проверок на четность вида:

mod2, (g)

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

Синдромное декодирование в точности определено приведенным выше процессом декодирования в рамках обобщенного алгоритма.

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

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

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

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

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

При этом матрица в может быть задана тремя способами:

где !к - единичная матрица;

Р1>г - матрица проверочных элементов, полученная посредством деления строк единичной матрицы на порождающий полином;

0. = [1к,Рк,г],

(9)

*'в(*)

(Ю)

а^РьРЧЛ.

где ?\,г - матрица проверочных элементов, определяемая при помощи (6).

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

Теорема. Быстродействие кодера несистематического кода определяется максимальным весом W(x')rms линейных булевых функций, определяющих структуру кодера, при этом значение W(x') не превосходит

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

Для трех последних способов проведения предварительных вычислений техническая реализация кодеров предполагает использование ПЛМ, БМК и FPGA, программируемых в соответствии с конкретной полученной системой булевых функций, т.е. сводится к параллельным вычислениям, отображаемым на регулярные систолические структуры. Их быстродействие будет эквивалентно быстродействию схемы на базе ПЗУ и как минимум на порядок выше этого показателя в традиционном исполнении. В общем случае быстродействие зависит от параметров блока, а именно от соотношения ляг, поскольку время цикла кодирования для традиционной схемы пропорционально 2п, а в предложенных алгоритмах для наилучшего случая - г/2. Так как в соответствии с теоремой Шеннона при неограниченном увеличении л требуемая достоверность может быть достигнута при сколь угодно малой избыточности fr/n), то, следовательно, и получаемый при этом выигрыш предложенных алгоритмов по быстродействию будет увеличиваться По сравнению с традиционными последовательными методами.

На основе теории управляющих систем произведена оценка сложности разработанных быстрых кодеров, которая в общем случае определяете* по порядку как

(12)

(13)

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

1. Вычисление синдрома.

2. Вычисление многочлена, имеющего своими корнями локаторы ошибок.

3. Нахождение корней данного многочлена.

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

5. Исправление ошибок.

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

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

(14)

¡=■1

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

1С-

2

к

где т - степень расширения поля ОР(2°'), соответственно для кодов БЧХ и РС.

При этом проверочная матрица Н для кодов БЧХ может быть задана тремя способами:

Н|-[РТ,*.Ц. (15)

И(х)х'~

Ь(х)х"

. к(х)х

(16)

\ а а1 . а „ 1 а2 (а2)2 . (а2Г'

1 а2' (а2')2 . (а2')-1 где I - число исправляемых кодом ошибок;

а - примитивный элемент конечного расширенного поля, используемого дня построения кода БЧХ.

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

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

Для кодов РС проверочные матрицы определены аналогично (15)-(17) с использованием вычислительных операций в конечных полях ОР(2т) с последующим приведением к двоичному виду для упрощения технической реализации и возможности использования в этих целях параллельных систолических структур.

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

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

Третий вариант реализации предполагает преобразование координат у, непосредственно в компоненты <5ь 1» 1, п. Таким образом, необходимо получить следующую систему булевых функций:

в, =Ш,Д 1-ТИ (18)

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

ъ-т,)). У =7(1У)

путем определения зависимостей

»(20)

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

{у,)->№->{в1 (21)

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

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

Оценена сложность такого декодера В общем случае она равна по порядку

Цп)»Г (22)

и ¿РС(п)*2"т (23)

для кодов БЧХ и РС соответственно.

Показано, что использование минимизации и приведения кодов РС к двоичному ви' ду значительно снижает сложность реализации по сравнению с (22) и (23).

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

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

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

Для этого кода вероятность неправильного приема блока определяется по формуле:

Рсггы = (К - 4П')0,54п + [1 - (Л - 4«')0,54"']£ Сп[ 1 - (1 - Ро)' ]'(1 - РоГЛ (24)

'-3

где N - общая длина составного комбинированного кода (в битах); п1 - длина блока кода Голея, используемого для синхронизации; ро - средняя вероятность ошибки на бит; п - длина блока кода РС, выраженная в байтах.

Применение этого кода позволяет повысить достоверность передачи данных по реальным каналам, в том числе и высокоскоростным с применением технологии АТМ.

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

ш

2>,

где Р( е {Ро, Р|,..., Рг. Р®И

«- число используемых базисных последовательностей.

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

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

14

выводы

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

Непосредственная техническая реализация осуществляется с использованием современной элементной базы широкого назначения, в виде СБИС с регулярной структурой, что позволяет снизить себестоимость соответствующих устройств в несколько раз по сравнению с традиционной реализацией в виде заказных СБИС. Рассмотрены различные варианты кодеков как в смысле процессов их синтеза, так и в смысле их технической реализации с применением ПЗУ, ПЛМ, БМК и ИРСА.

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

Применение предложенных алгоритмов синтеза позволяет значительно упростить процедуру проектирования кодеков, особенно для кодов РС за счет приведения аналитических выражений в поле Галуа к двоичной форме, и приводит к чрезвычайно простой технической структуре кодеков, которая для малых и средних длин кодовых блоков реализуется на одной СБИС. Решена нетривиальная задача синтеза декодеров в виде единой комбинационной схемы, а также в виде структур ВС-ПЗУ и ВС-ПЛМ.

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

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

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

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

СПИСОК ОПУБЛИКОВАННЫХ АВТОРОМ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. A.c. 1727201 СССР. Н 03 М 13/00. Помехоустойчивый кодек для передачи дискретных сообщений / Ассанович Б.А., Ситкевич Т.А, (СССР). - № 4851062/24; Заявлено 10.07.90; Опубл. 15.04.92. Бюл. № 14,- 7 с.

2. Ситкевич Т.А., Сюрин В.Н. Применение распознавания образов в помехоустойчивом кодировании. // Физика быстропротекающих плазменных процессов; Тез. докл. 111 Межреспубликанского Семинара. - Гродно: изд. ГрГУ. 1992. - С.50.

3. Сюрин В.Н., Ситкевич Т.А. Методические указания к практическим занятиям по спецкурсу «Статистическая радиофизика и теория информации». - Гродно: изд. ГрГУ, 1992. -36 с.

4. Сюрин В Н., Копылова Т.И., Ситкевич Т.А. Формирование последовательностей псевдослучайных чисел с заданной вероятностью появления единичных символов. // Сов-

6. Сюрин В.Н., Ситкевич Т.А. Выбор структуры быстродействующих декодирующих устройств. //Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления: Материалы НТК. - Мн.: изд. БГУ, 1995. - С. 69-73.

7. Ситкевич Т.А. Оценка сложности комбинационных декодирующих схем./ Организация и технология средств связи: Материалы Республиканского научно-технического семи-кара-сессинУ/Весшк сувязи -1996, Na 2. - С. 15.

8. Сюрин В.Н., Ситкевич Т.А. Лабораторный практикум по курсу «Статистическая радиофизика и теория информации». - Гродно: изд. ГрГУ, 1996. - 34 с.

9. Сюрин В.Н., Карнаухов Н.В., Ситкевич Т.А. Кодирование данных с исправлением ошибок для удаленных терминалов. // Новые информационные технологии в образовании: Труды Второй Международной конференции. - Мн.: изд. БГЭУ, 1996. - С. 115-117.

10. Ситкевич Т.А. Количественная оценка быстродействия кодеков в виде комбинационных структур. / Современные средства связи: Материалы Второй Международной научно-технической конференции. // Специальный выпуск журнала «Известия Белорусской Инженерной Академии» -1997, № 1(3/1). - С. 97-100.

11. Сюрин В.Н., Ситкевич Т.А. Приведение недвоичной структуры быстродействующих кодеков к двоичной форме. / Современные средства связи: Материалы Второй Международной научно-технической конференции. // Специальный выпуск журнала «(Известия Белорусской Инженерной Академии» - 1997, № 1(3/1). - С. 104-106.

17

РЭЗЮМЭ Сггкевт Таццяма Анатольеуна ХУТКАЕ С1НДРОМНАЕ ДЭКАД31РАВАШЕ Л1ПЕЙНЫХ БЛОКАВЫХ КОДАУ БЧХ I РС

Ключавыя словы: Ыфармацыя, даныя, кодэр, дэкодэр, выпрауленне памылак, код БЧХ, код РС, код Гале«, канечныя пал>, булеуск!« функцьн, мш1м1зацыя, камбшацыйная структура, ¡м!тацыйная мадэль, ¡мавернасць памылак.

Аб'ектам даследавання прадстауленай работы з'яуляюцца сучасныя кодавыя канструкцьц 1 спосабы ¡х рэалпацьа у с!стэмах сувяз1 \ «¡равания.

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

Пры даследаванш выкарыстоуваш'ся метады аналЬу I Ынтэзу на аснове вектарна-матрычнай алгебры, булеускай логш, тэорьп канечных палеу I фармальных палшомау; а таксама метады ¡М1тацыйнага I ¡мавернасна-статыстычнага мадэлфавання. Выкарыстоуваемая апаратура - перса-нальны камп'ютар.

У рабоце нрапанаваиы якасна новы прынцып праектавання кодэкау, ям заключаешь у пра-вядзенш папярэдшх специальных вьшчэнняу, як!я традыцыйиа выконваюцца непасрэдна у пра-цэсе дэкадзфавання; вынЫ як|'х I вызначаюць схемную рэалЬацыю адпаведных уладкаванняу, ларалельных па уваходу I выхаду 1 валодаючых макамальным хуткадзеяннем.

Прапанаваныя алгарытмы вьшчэнняу I канкрэтных тэхжчных прыемау у працэсе праекта-оання кодэкау даюць магчымасць ¡х рэа/шацьп на сучаснай элементнай базе щырокага иазначэння у выглядзе ЗВ1С з рэгулярнай структурам, што дазваляе у некальк1 разоу знЫць яе кошт у пзра-унанш з заказным! В1С.

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

Вынш работы выкарыстаны у дз/б НДП «Распрацоука элементау шфармацыйных тэхна-лопй», № ДзР 19961190, а таксама у вучыбным працэсе, што пацвярджаецца наяуным! актапп ука-ранення.

Галща скарыстання - ¡нфармацыйныя тэхналогн, працэсы абмену даным! у вьшчальиых сетках, а таксама у слецыя/тьных сгстэиах сувяз11 к!равання

18

РЕЗЮМЕ Ситкевич Татьяна Анатольевна БЫСТРОЕ СИНДРОМНОЕ ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ БЧХ И РС

Ключевые слова: Информация, данные, кодер, декодер, исправление ошибок, код БЧХ, код РС, «сод Голе*, конечные пол», булевы функции, минимизации, комбинационная структура, имитационная модель, вероятность ошибки.

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

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

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

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

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

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

Результаты работы использованы в г/б НИР «Разработка элементов информационных технологий», № ГР 19961190, а также в учебном процессе, что подтверждается имеющимися актами внедрения.

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

19

RESUME Sitkevich Tatyana Anatolyevna FAST SYNDROME DECODING OF LINEAR BLOCK DCH AND RS CODES

Key words: Information, data, encoder, decoder, error correction, BCH code, RS code, Golay code, finite fields, Boolean functions, minimization, combinative structure, imitation model, probability of errors.

The object of the research presented is study of modern code constructions and the methods of their realization in the system of communication and control.

This study aims to elaborate new algorithmic and technical scheme solutions which would allow to reach the potentially possible fast-acting for the encoders and decoders of the most important classes of linear block BCH and RS codes.

The following methods of research haye been used for that purpose: the analysis and synthesis on the basis of vector-matrix algebra, Boolean logics, the theory of finite fields and formal polynomials, as well as the methods of imitation and statistical probability modeling. A personal computer has been used as the equipment.

The research offers a qualitatively new projection of encoders and decoders, which involves the conduct of preliminary special calculations, traditionally carried out directly during the decoding process The results of these calculations will determine the scheme realization of the corresponding device, parallel as to the input and output and possessing maximum fast-acting.

The algorithms of the calculations and concrete techniques in the projections of encoders and decoders offered allow their realization on the modem element basis of a wide profile in the shape of VLSI with regular structure which in turn allows a several times' lower cost as compared to the LSI made to order.

The elaborated statistical probability model for the imitation of the processes of data exchange allows to estimate the efficiency of code constructions without using the real channel, which may imply difficulties in certain cases.

The results of the study have been made use of in the state-funded scientific research «The Elaboration of the Information Technologies Elements» (the state registration # 19961190) and also in educational process, which is being proved by the existing acts of incorporation. '

The sphere of utilization includes information technologies, data exchange in calculation scheme and in special communication and control systems.

СИТКЕВИЧ Татьяна Анатольевна

БЫСТРОЕ СИНДРОМНОЕ ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ

Специальность 05.12.17 -Радиотехнические и телевизионные системы и устройства

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

Подписано в печать 03.02.98. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Усл„печ.лД,28. Уч.-изд.л. 1,0. Тираж 90 экз. Заказ 64.

Белорусский государственный университет инборматики и радиоэлектроники

Отпечатано в БШР. 220027, Минск, П.Бровкк, £