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

Размещено на http://www.allbest.ru/

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

УДК 004.052.4

Автореферат диссертации

на соискание ученой степени кандидата технических наук по специальности 05.13.17 - «Теоретические основы информатики»

МЕТОДЫ И КОМПЬЮТЕРНЫЕ МОДЕЛИ ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ НА ОСНОВЕ ИЗБЫТОЧНОГО ИТЕРАТИВНОГО КОДИРОВАНИЯ И ПЕРЕМЕЖЕНИЯ ДАННЫХ

Шиман Дмитрий Васильевич

Минск 2009

Работа выполнена в Учреждении образования «Белорусский государственный технологический университет»

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

Официальные оппоненты: ЛИСТОПАД Николай Измаилович, доктор технических наук, профессор, директор Учреждения «Главный информационно-аналитический центр Министерства образования Республики Беларусь»;

Осипов Анатолий Николаевич, кандидат технических наук, доцент,

первый проректор Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники».

Оппонирующая Академия управления при Президенте организация - Республики Беларусь.

Защита состоится 15 мая 2009 г. в 10.00 часов на заседании совета по защите диссертаций Д 02.01.02 при Белорусском государственном университете по адресу: 220030, г. Минск, ул. Ленинградская, 8 (корпус юридического факультета), ауд. 407, тел. ученого секретаря 209-57-09.

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

Автореферат разослан «9» апреля 2009 г.

Ученый секретарь совета по защите диссертаций кандидат физ.-мат. наук доцент Е.С. Чеб

ВВЕДЕНИЕ

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

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

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

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

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

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

Указанные особенности и определяют направление исследований настоящей диссертационной работы.

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

Связь работы с крупными научными программами, темами

Исследования проводились в рамках научно-исследовательских госбюджетных тем: ГБ 24-148 (№ ГР 20041608) «Разработка методов анализа и синтеза адаптированных турбо кодов для высокопродуктивных систем передачи и переработки информации» (2004-2006) и ГБ 26-114 (№ ГР 20063589) «Разработка и исследование методов преобразования информации на основе помехоустойчивых кодов и шифрования данных с использованием нейросетевых технологий» (2006-2008), выполненных на кафедре информационных систем и технологий УО «Белорусский государственный технологический университет».

Цель и задачи исследования

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

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

1) проанализировать современное состояние проблемы передачи информации и путей реализации помехоустойчивого приема и перемежения данных;

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

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

4) исследовать свойства и граничные характеристики разработанных кодов для систем хранения и передачи данных;

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

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

Положения, выносимые на защиту

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

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

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

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

Личный вклад соискателя

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

Апробация результатов диссертации

Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: IV, V International Symposium “New electric and electronic technologies and their industrial implementation” (Zakopane, Poland, 2005, 2007); Международная научно-техническая конференция «Организационно-техническое управле-ние в межотраслевых комплексах» (Минск, БГТУ, 2004); IX Республиканская научная конференция студентов и аспирантов высших учебных заведений Республики Беларусь «НИРС-2004» (Гродно, ГрГУ, 2004); Х Республиканская научная конференция студентов и аспирантов высших учебных заведений Республики Беларусь «НИРС-2005» (Минск, БГУИР, 2006); Международная научно-техническая конференция «Автоматический контроль и автоматизация производственных процессов» (Минск, БГТУ, 2006); Республиканская конференция «Информационные технологии управления в экономике - 2006» (Брест, БрГУ, 2006); Республиканская конференция «Информационные технологии управления в экономике - 2007» (Брест, БрГУ, 2007); Международная научно-техническая конференция «Организационно-техническое управление в межотраслевых комплексах» (Минск, БГТУ, 2007); 62, 63, 64, 65-ая конференция БГТУ (Минск, БГТУ, 2005-2008); IV Международная конференция «Информационные системы и технологии» (IST' 2008) (Минск, БГУ, 2008).

Опубликованность результатов диссертации

Результаты диссертации опубликованы в 18 научных работах, из которых 5 - статьи в научных журналах в соответствии с п.18 Положения о присуждении ученых степеней и присвоении ученых званий в Республике Беларусь (общим объемом 1,8 авторских листа), а также 7 статей в сборниках материалов научных конференций, 4 тезисов и 2 патента.

Структура и объем диссертации

Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения, библиографического списка и приложений. Общий объем диссертации составляет 147 страниц, в том числе 38 рисунков на 14 страницах, 28 таблиц на 11 страницах, 2 приложения на 38 страницах. Количество использованных библиографических источников составляет 120 (включая собственные публикации автора) на 10 страницах.

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

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

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

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

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

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

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

Существующие программные комплексы (MathCAD, MathLab и др.), с помощью которых возможна реализация имитационной модели, не всегда позволяют это сделать в полном объеме. Весьма затруднительным является внедрения в программную среду блоков, реализующих тот или иной процесс, разработанный пользователем. Таким образом, существует необходимость в разработке авторской компьютерной имитационной модели для исследования свойств системы передачи данных с использованием разработанных в диссертации помехоустойчивых кодов и перемежителей данных.

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

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

Выбираются взаимно простые числа pm и qm, такие, что nm = pm . qm.

Затем вычисляется tm = (pm-1) . (qm-1). После чего находятся два простых числа (em и dm) таких, чтобы em . dm mod tm = 1.

Упомянутые пары чисел генерируются и используются отдельно и независимо для строк и для столбцов матрицы данных. Конечным итогом выполнения операций является набор em и dm, которые, по аналогии с алгоритмом шифрования RSA, используются при прямом (перемежении) и обратном (деперемежении) преобразованиях. В соответствии с этим и в отличие от метода RSA, в нашем случае необходимо вычислить не одну, а две пары значений em и dm: одна - для операций над строками (e1, d1), другая - для операций над столбцами (e2, d2). Количество строк и количество столбцов перемежителя определяется соответственно: nr=n1 - 1, nc=n2 - 1.

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



Рисунок 1 - Принцип перестановки строк и столбцов матрицы данных: а) перемежение строк; б) перемежение столбцов

Проанализируем их использование в упомянутых операциях. Рассмотрим перемежение строк. Перемежение i-строки множества {si} (1?i?nr) осуществляется на основе формулы:

Данная формальная запись означает, что i-я строка исходной матрицы переместится на j-ю позицию после перемежения.

Второй этап перемежения связан с обработкой столбцов. Новое местоположение столбца множества {sty} (1?y?nc) определяется согласно формальной записи:

Запись (2) означает, что y-й столбец исходной матрицы переместится на z-ю позицию после перемежения.

В данной главе описан алгоритм и устройство (защищено патентом [17]), реализующий данный метод перемежения. Рассмотрим его работу в режиме считывания (перемежения).

Устройство (рисунок 2) содержит блок определения степенных коэффициентов (ОСК), в котором формируются данные на управляющие входы d1 и d2 генератора адресов, исходя из значений размера матрицы nr и nc. Сформированные значения d1 и d2 из блока ОСК поступают на выходы генератора адресов (ГА). ГА принимает значения размера матрицы nr и nc, степенных коэффициентов и тактовые импульсы. В результате работы ГА на его выходе формируются значение адреса считывания, поступающего на вход блока памяти. Счетчик подсчитывает входные тактовые импульсы и выдает соответствующее значение на адресные входы блока памяти в виде значения адреса записи. Указанный блок последовательно запоминает входные битовые символы при работе в режиме записи и выводит битовые символы в соответствии с адресом, обеспечиваемым генератором адресов.

Рисунок 2 - Структурная схема устройства строчно-столбцового перемежения данных [17]

Полагая, что k - адрес блока памяти, который изменяется от 0 до Nk - 1, путем несложных логических рассуждений приходим к выводу, что для определения последовательности номеров выходных бит блока памяти можно использовать формулу, содержащую следующие параметры: nr, nc, d1, d2, n1, n2:



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

Данная формула (3) означает, что v-ый двукратно перемеженный (по строкам и столбцам) бит последовательности будет считан на выходе устройства под k-ым номером (adrk).

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

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

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

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

В третьей главе рассмотрены конструкции и свойства новых двумерных линейных итеративных кодов с двойными диагональными проверками (ЛИКДД) и с объединенными диагональными проверками (ЛИКОДД), отличающиеся от известных итеративных кодов увеличенным минимальным кодовым расстоянием и временем кодирования. Проанализированы ЛИКДД и ЛИКОДД с полными и усеченными проверочными матрицами.

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

Проверочную матрицу ЛИК можно дополнить избыточными символами, обеспечивающими проверку на четность (нечетность) по двум диагоналям. Так, например, при кодировании информационного слова U = 0111101000101100 с помощью таблицы с четностью по строкам, столбцам и диагоналям получим избыточные символы Ur = Uh, Uv, Ud1, Ud2, Us = 0011 1010 0011000 1111011 0 как показано на рисунке 3 (информационные символы выделены жирным шрифтом, а проверочные - курсивом, менее контрастно).

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

В общем случае линейный двумерный итеративный код с двойными диагональными проверками (ЛИКДД) (по основанию два) можно определить как блоковый (n1, k1, n2, k2) код, формирующий кодовые последовательности длиной k (k=k1k2) информационных и 3•(k1+k2) - 1 проверочных разрядов (в приведенном примере k1=k2=4).

В работе приведены основные параметры ЛИКДД. Пусть число информационных символов равно k (k=k1k2). Тогда избыточность (r), длина кодовой последовательности (n) и степень кодирования (R) равны:

Величина относительной избыточности, под которой будем понимать отношение числа избыточных бит (r) к длине (числу бит) кодовой комбинации (n), равна:

Анализ зависимости величины rотн от длины информационной последовательности (k) (рисунок 4) показал, что с ростом k наблю дается уменьшение rотн: при k>512 бит число избыточных символов по сравнению с n настолько мало, что составляет несколько процентов, а при k?512 - избыточность достаточно велика (десятки процентов).

Утверждение 1. Минимальное кодовое расстояние двумерного линейного итеративного кода с двойными диагональными проверками равно шести (d=6).

Доказательство данного ут- верждения основывается на определениях расстояния и веса Хэмминга.

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

Доказательство данного утверждения основывается на теореме, которая гласит, что код с минимальным расстоянием d может исправлять [(d-1)/2] ошибок. Если d четное, то код может одновременно исправлять (d-2)/2 и обнаруживать d/2 ошибок.

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

На основе линейного итеративного кода с двойными диагональными проверками разработано запоминающее устройство, которое защищено патентом РБ [18].

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

Избыточность, длина кодовой последовательности и степень кодирования ЛИКОДД равны соответственно:

Рисунок 5 - Объединенные диагональные проверки ЛИКОДД

Величина относительной избыточности равна:

Из утверждения 1 следует, что минимальное кодовое расстояние двумерного линейного итеративного кода с объединенными двойными диагональными проверками равно шести (d=6).

Из утверждения 2 следует, что двумерный линейный итеративный код с объединенными диагональными проверками (d=6) позволяет обнаруживать все тройные ошибки и корректировать все одиночные и двойные ошибки.

Сравнительный анализ относительной избыточности кода и времени формирования проверочных символов приведены в таблицах 1 и 2 соответственно.

Таблица 1 - Относительная избыточность кодов

Длина, k	Размерность кода, k1 Ч k2	Относительная избыточность, rотн
		ЛИК	ЛИКД	ЛИКДД	УЛИКДД	ЛИКОДД	УЛИКОДД
16	4 Ч 4	0,360	0,500	0,590	0,578	0,515	0,500
64	8 Ч 8	0,210	0,333	0,423	0,418	0,340	0,333
128	16 Ч 8	0,163	0,304	0,357	0,353	0,308	0,304
256	16 Ч 16	0,114	0,200	0,271	0,268	0,202	0,200
512	16 Ч 32	0,087	0,179	0,218	0,217	0,137	0,179
1024	32 Ч 32	0,060	0,111	0,157	0,156	0,112	0,111
4096	64 Ч 64	0,031	0,058	0,086	0,085	0,059	0,058

Время формирования проверочных символов (таблица 2) у ЛИК, ЛИКД, ЛИКДД и ЛИКОДД в два раза больше, чем у УЛИКДД и УЛИКОДД из-за отсутствия у последних контрольного бита матрицы.

Таблица 2 - Время (в тактах) формирования проверочных символов

Длина, k	Размерность кода, k1 Ч k2	Время формирования проверочных символов, такт
		ЛИК	ЛИКД	ЛИКДД	УЛИКДД	ЛИКОДД	УЛИКОДД
16	4 Ч 4	4	4	4	2	4	2
64	8 Ч 8	6	6	6	3	6	3
128	16 Ч 8	7	7	7	4	7	4
256	16 Ч 16	8	8	8	4	8	4
512	16 Ч 32	9	9	9	5	9	5
1024	32 Ч 32	10	10	10	5	10	5
4096	64 Ч 64	12	12	12	6	12	6

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

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



Рисунок 6 - Схемы передачи информации: а - на основе кодера/декодера и перемежителя/деперемежителя; б - на основе только кодера/декодера

Для исследования эффективности комплексного преобразования данных на основе кодирования и перемежения данных, в том числе - на основе разработанных в диссертационной работе кодов и перемежителей, в разработанной компьютерной модели выполнена имитация функционирования двух схем передачи информации, представленных на рисунке 6. Компьютерная имитационная модель передачи информации реализована в среде Delphi 7 (рабочее название «Имитатор»). Результат работы модели отображен на рисунке 7.

Рисунок 7 - Интерфейс программного средства «Имитатор»

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

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

Таким образом, комплексное преобразование информации на основе строчно-столбцового перемежения данных и итеративного кодирования (УЛИКОДД) позволяет корректировать большее количество ошибочных бит в передаваемом сообщении произвольной длины и за меньшее время, чем совместное использование известных методов итеративного кодирования и перемежения информации.

ЗАКЛЮЧЕНИЕ

Основные научные результаты диссертации

1. Разработан новый метод строчно-столбцового перемежения данных, основанный на использовании пар взаимно простых чисел и отличающийся от известных методов подобного вида обеспечением более высокого минимального расстояния разнесения группирующихся ошибок: в 1.5-2.0 раза. Устройство, в котором реализован метод, защищено патентом РБ [1, 2, 9, 13, 15, 17].

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

Разработано и защищено патентом Республики Беларусь запоминающее устройство, в котором реализован двумерный линейный итеративный код с двойными диагональными проверками с полной и усеченной проверочной матрицей [18].

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

Показана возможность использования усеченного двумерного линейного итеративного кода с объединенными диагональными проверками на четность в системе турбо кодирования [4, 6-8, 14, 16].

4. Разработана компьютерная имитационная модель передачи информации, которая позволяет оценить качество передачи данных с различными параметрами усеченного линейного итеративного кода с объединенными диагональными проверками и блока перемежения, а также программное средство для расчета и моделирования процессов перемежения [5, 11, 12].

Совместное использование разработанных кодов и метода перемежения позволяет корректировать от 5 до 75 раз больше ошибочных бит, чем в случаях использования комплексного преобразования информации на основе известных итеративных кодов и известных методов перемежения данных [5].

Рекомендации по практическому использованию результатов

Результаты работы получены и реализованы в рамках госбюджетных НИР: ГБ 24-148 и ГБ 26-114, выполняемых на кафедре информационных систем и технологий УО «Белорусский государственный технологический университет».

На основе предложенных в работе решений:

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

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

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

1) при моделировании процессов передачи данных по сети Юнибел и повышении эффективности работы сервера учреждения «Главного информационно-аналитического центра Министерства образования Республики Беларусь», обеспечивающего функционирование локальной сети центра;

2) при повышении эффективности работы сервера ИП «Айтос», обеспечивающего функционирование локальной сети;

3) при передаче информации между Интернет-сервером Республиканского института профессионального образования и учреждениями, обеспечивающими получение профессионально-технического и среднего специального образования;

4) в учебном процессе УО «Белорусский государственный технологический университет».

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

Статьи в научных журналах

Шиман, Д.В. Метод псевдонеравномерного перемежения символов турбокода / Д.В. Шиман // Труды БГТУ. Сер VI Физ.-мат. науки и информатика. - 2005. - Вып. XIII. - С. 168-170.

Шиман, Д.В. Комплексное преобразование символов перемежителя и метод сжатия LZ / Д.В. Шиман // Труды БГТУ. Сер VI Физ.-мат. науки и информатика. - 2006. - Вып. XIV. - С. 136-138.

Шиман, Д.В. Свойства и параметры линейных итеративных кодов с двойными диагональными проверками / Д. В. Шиман, Д. М. Романенко // Труды БГТУ. Сер. VI, Физ.-мат. науки и информатика. - 2007. - Вып. XV. - С. 151-154.

Multilevel turbocoding schemes on the basis of twodimensional linear iterative codes with diagonal checks / D.V. Shiman, D.M. Romanenko, N.V. Patsei, P.P. Urbanovich // Przeglad elektrotechniczny. - 2008. - № 3. -P. 152-154.

Шиман, Д.В. Компьютерная имитационная модель передачи информации на основе перемежителя и двумерного линейного итеративного кода с объединенными двойными диагональными проверками / Д. В. Шиман // Труды БГТУ. Сер. VI, Физ.-мат. науки и информатика. - 2008. - Вып. XVI. - С. 133-136.

Статьи в материалах научных конференций

Структура графического интерфейса и функциональной спецификации программного средства моделирования сигнально-кодовых конструкций на основе турбо кода / Д.В. Шиман, П.П. Урбанович, Н.В. Пацей, К.С. Мишин // Организационно-техническое управление в межотраслевых комплексах: Материалы Междунар. науч.-тех. конф., Минск, 28-29 октября 2004г. - Минск: БГТУ, 2004. - С. 217-219.

Использование многоуровневых турбокодов в системах передачи двоичных данных / Д.В. Шиман, П.П. Урбанович, Н.В. Пацей, Д.М. Романенко // Автоматический контроль и автоматизация производственных процессов: материалы Междунар. науч.-тех. конф., Минск, 6-8 июня 2006г. - Минск: БГТУ, 2006. - С. 206-208.

Шиман, Д.В. Исследование основных характеристик многоуровневых турбокодов / Д.В. Шиман, П.П. Урбанович, Н.В. Пацей, Д.М. Романенко // Автоматический контроль и автоматизация производственных процессов: материалы Междунар. науч.-тех. конф., Минск, 6-8 июня 2006г. - Минск: БГТУ, 2006. - С. 199-202.

Шиман, Д.В. Перемежители в турбокодировании / Д.В. Шиман, А.Н. Матерова // Организационно-техническое управление в межотраслевых комплексах: материалы докладов II Междунар. науч.-тех. конф., Минск, 20-21 ноября 2007г. - Минск: БГТУ, 2007. - C. 408-411.

Шиман, Д.В. Двумерный линейный итеративный код с объединенными диагональными проверками. / Д.В. Шиман, Д.М. Романенко // Информационные технологии управления в экономике' 2007: Респ. науч.-практ. конф., Брест, 24-25 апреля 2007г. - Брест: Изд-во БрГУ, 2007 - С. 81-84.

Шиман, Д.В. Алгоритмы и программные средства моделирования систем передачи криптографической информации на основе нейросетевых технологий / Д.В. Шиман, Е.В. Лисица // Организационно-техническое управление в межотраслевых комплексах: материалы докладов II Междунар. науч.-тех. конф., Минск, 20-21 ноября 2007г. - Минск: БГТУ, 2007. - C. 399-404.

Шиман, Д.В. Метод преобразования цифровой информации на основе псевдослучайного перемежения и линейного итеративного кодирования с объединенными диагональными проверками / Д.В. Шиман, Д.М. Романенко // Информационные системы и технологии (IST'2008): IV Междунар. конф., Минск, 4-6 ноября 2008г. - Минск: БГУ, 2008. - С. 95-100.

Тезисы докладов в материалах научных конференций

Shyman, D.V. System of the information on the basis of a turbo coding in Matlab enviroment. / D.V. Shyman, N.V. Patsey, P.P. Urbanovich // News electrical and electronic technologies and their industrial implementation: IV International Conference NEET'2005, Zakopane, Poland, 21-24 june 2005.- Zakopane, 2005. - P. 89.

Шиман, Д.В. Перемежение символов турбокода псевдонеравномерным методом / Д.В. Шиман // Х Республиканская научная конференция студентов и аспирантов высших учебных заведений Республики Беларусь «НИРС-2005», Минск, 14-16 февраля 2006г. - Минск: БГУИР, 2006. - С. 148.

Шиман, Д.В. Комплексное преобразование символов блока перемежения с последующим сжатием на основе метода LZ. / Д.В. Шиман // Информационные технологии управления в экономике - 2006: Респ. науч.-практ. конф. - Брест: БрГУ, 2006. - С. 39.

Shiman, D.V. Multilevel turbocoding schemes on the basis of twodimensional linear iterative codes with diagonal checks / D.V. Shiman, D.M. Romanenko, P.P. Urbanovich // News electrical and electronic technologies and their industrial implementation: V International Conference NEET'2007. - Zakopane, 2007. - P.97.

Патенты

Устройство перемежения/обратного перемежения для систем связи: пат. 11268 Республики Беларусь, МПК Н 03 М 13/00 / Д.В. Шиман, Н.В. Пацей, Д.М. Романенко, П.П. Урбанович; заявитель Бел. гос. технолог. ун-т. - № а 20070136; заявл. 08.02.07; опубл. 05.08.08. // Афiцыйны бюл. / Нац. цэнтр iнтэлектуал. уласнасцi. - 2008. - № 3. - С. 74.

Запоминающее устройство: пат. 11406 Республики Беларусь, МПК H 03 М 13/00, G 11C 11/00 / Д.В. Шиман, Н.В. Пацей, Д.М. Романенко, П.П. Урбанович; заявитель Бел. гос. технолог. ун-т. - № а 20070664; заявл. 31.05.07; опубл. 05.09.08. // Афiцыйны бюл. / Нац. цэнтр iнтэлектуал. уласнасцi. - 2008. - № 4. - С. 48.

АННОТАЦИЯ

Метады і Камп'ютэрныя імітацыйныя мадэлi ПЕРАЎТВАРЭННЯ ІНФАРМАЦЫІ НА АСНОВЕ ЗАЛІШНЯГА ІТЭРАТЫЎНАГА КАДЗІравання І ПЕРАМЯЖЭННЯ ДАДЗЕНЫХ

Ключавыя словы: перамяжыцель, лінейны ітэратыўны код, імітацыйнае мадэляванне, комплекснае пераўтварэнне, памехаўстойлівае кадзіраванне.

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

Атрыманыя вынікі і іх навізна. У працы праведзены аналіз існых асноўных уласцівасцяў, алгарытмы кадавання і декодирования якія карэктуюць кодаў а таксама метадаў перамяжэння дадзеных, выкарыстоўваных у каналах перадачы і сістэмах захоўвання дадзеных.

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

Вынікі дысертацыйнай працы ўкаранёныя і выкарыстоўваюцца пры перадачы інфармацыі паміж Інтэрнэтам-серверам Рэспубліканскага інстытута прафесійнай адукацыі і ўстановамі, забяспечвальнымі атры-манне прафесійна-тэхнічнай і сярэдняй адмысловай адукацыі, а таксама ў вучэбным працэсе УА "Беларускі дзяржауны тэхналагічны ўніверсітэт".

Методы и Компьютерные модели преобразования информации на основе избыточного ИТЕРАТИВНОГО кодирования и перемежения данных

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

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

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

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

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

Methods and Computer models of transformation of the information on the basis of REDUNDANCY ITERATIVE coding and interleaving data

Keywords: interleaver, a linear iterative code, imitating modelling, complex transformation, noiseproof coding.

The work purpose is working out complex research of transformation methods of the digital information on a basis interleaving transferred symbols and superfluous coding for correction of repeated errors in transfer and data storage systems. In the given dissertational work objects of research are methods and means of increasing the reliability of transfer and information storage. Objects of research are interleavings and linear iterative codes for systems of transfer and information storage.

The received results and their novelty. In the work the analysis of existing basic properties, algorithms of coding and decoding of correcting codes and also methods interleaving data used in channels of transfer and systems of a data storage is carried out.

The new method row-column interleaving data, steam of mutually simple numbers based on use is developed. Designs of new two-dimensional linear iterative codes with double diagonal checks with the full and truncated verifying matrix are developed and investigated. Designs of new two-dimensional linear iterative codes with incorporated double diagonal checks with the full and truncated verifying matrix are developed and investigated. The computer imitating model of an information transfer which allows to estimate quality of data transmission with various parameters of the truncated linear iterative code with incorporated diagonal checks and the block interleaving is developed.

The results of work are introduced and used at an information transfer between the Internet server of Republican institute of vocational training and the establishments providing reception of the professional and average vocational education, and also in educational process in the Belarussian state technological university.

Размещено на Allbest.ru

...