Введение к работе
Актуальность проблемы. Уровень и темпы развития современных информационных систем ставят их разработчиков перед необходимостью решения задачи повышения достоверности информации передающейся, хранящейся и обрабатывающейся в таких системах. Разнообразие электронной аппаратуры, использующейся в информационных системах, приводит к необходимости описания различных дискретных каналов передачи информации.
Для осуществления надежной передачи по конкретному каналу необходимо решить два основных вопроса. Во-первых, подобрать метрическое описание (метрику), наилучшим образом отражающее вероятностную природу искажений в канале, и, во-вторых, построить в выбранной метрике код, обладающий корректирующей способностью, которая бы обеспечивала требующийся уровень надежности.
На сегодяшний.день имеет место следующая ситуация. С одной стороны широко развит аппарат, позволяющий для дискретного канала, описывающегося метрикой Хэмминга, производить выбор подходящего кода с исправлением заданного числа ошибок в указанной метрике. С другой стороны, существует, целый ряд дискретных каналов для которых либо вообще не дано удовлетворительного метрического описания, либо для такого описания неизвестны достаточно мощные семейства корректирующих кодов.
Таким образом, актуальной задачей является выбор кодов, исправляющих ошибки в нехэмминговых ментиках, а также построение процедур кодирования и декодирования таких кодов, обладающих полиномиальной сложностью.
цель работы. Целью настоящей работы является построение и
-2~
исследование кодов, обладающих полиномиальными процедурами кодирования и декодирования, в таких метриках, как модульная, метрика Ли, метрика битовых сдвигов, метрика вставок и выпадений символа 0 и метрика ошибок оператора,.а также мощностных оценок кодов в данных метриках.
Основными ыетодани исследования являются теоретические исследования с использованием методов теории кодирования, алгебры многочленов, теории вероятности, а также построение на персональном компьютере примеров полученных кодов.
Научная новизна работы заключается в следующем:
-получены новые семейства высокоскоростных кодов в модульной метрике, включающие в себя семейства кодов Дарьяна;
-на основе кодов в модульной метрике и введенного понятия гоморфности метрик построены новые семейства кодов в метрике Ли, метрике битовых сдвигов, метрике вставок и выпадений символа 0 и метрике ошибок оператора. Перечисленные семейства кодов имеют по сравнению с известными семействами либо меньшую избыточность, либо более широкое множество параметров;
-для построенных семейств кодов во всех указанных метриках разработаны алгоритмы кодирования и декодирования, имеющие полиномиальную сложность;
-построены границы для мощности и скорости кодов в модульной метрике; показано, что соответствующие границы в метрике Хэмминга являются их частным случаем;
-получены условия согласованности метрики вставок и выпадений символа 0 и метрики битовых сдвигов с дискретными каналами, которые описывают данные метрики; приведены критерии приближенного согласования указанных метрик и каналов для случая, когда условия согласованности не выполняются.
Практическая ценность работы состоит в том, что
разработка основных вопросов диссертации позволила:
-построить новые эффективные коды для передачи сообщений по широкому классу каналов;
-предложить методы кодирования и декодирования кодов, допускающие относительно простую программную или аппаратную реализацию кодирующего и декодирующего устройства.
-определить по вероятностным характеристикам дискретного канала какая из метрик, изучающихся в работе, является наиболее подходящей для описания такого канала;
-предоставить инженеру-разработчику возможность выбора конкретного кода с подходящими параметрами, исправляющего ошибки в любой из изучавшихся в работе метрик.
Тем самым расширена область использования кодов в системах передачи информации.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на int. workshop on Algebraic and Combinatorial Coding Theory, Bulgaria, 1992, на IEEE Information Theory Workshop, Japan, 1993, а также на семинаре по теории информации и кодирования кафедры АСУ СПИАП (Санкт-Петербург, 1993).
Публикации. По теме диссертации опубликовано б научных трудов в научно-технических журналах и сборниках докладов.
Новые результаты и положения, выносимые на защиту:
-методы построения корректирующих кодов в модульной
Метрике;
-понятие гомоморфности метрик и методы построения кодов в метриках, гомоморфных модульной;
-методы декодирования кодов в модульной метрике; -границы мощности и скорости кодов в модульной метрике; -условия согласованности метрик битовых сдвигов и вставок
символа 0 с дискретными каналами.
Структура и объем диссертации. Диссертация состоит из
введения, шести разделов, заключения, списка литературы и
приложений. Работа содержит 888 страницы основного текста, 4
рисунка, список использованной литературы содержит 50
наименований.
