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

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

1В13

/

Тугуж Уаэль Херндднн

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

г> и"^0 ¿и и У

О о

Ставрополь - 2008

003451613

Работа выполнена на кафедре «Автоматизированные системы обработки информации» Кабардино-Балкарского государственного университета им. Х.М. Бербекова (г. Нальчик)

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

кандидат технических наук, доцент Тлостанов Юрий Калиметович

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

доктор технических наук, профессор Исманлов Шейх-Магомед Абдулаевич

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

доктор технических наук, доцент Смирнов Александр Александрович

Институт информатики и проблем регионального управления КБ НЦ РАН (г. Нальчик)

Защита диссертации состоится « 27 » ноября 2008 г. в 16 00 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.256.08 при Ставропольском государственном университете по адресу: 355009, г. Ставрополь, улица Пушкина, 1, ауд. № 214.

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

Автореферат разослан « ¿2 » октября 2008 г.

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

канд. физ.-мат. наук, доцент Л^гг-^х ___Копыткова Л.Б.

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

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

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

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

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

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

Объектом исследования являются дискретные каналы передачи и хранения данных АСОИиУ.

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

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

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

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

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

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

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

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

6. Разработка прикладных программных средств, реализующих предложенные алгоритмы и методы коррекции многократных ошибок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

экспертизу и зарегистрированы при федеральной службе по интеллектуальной собственности, патентам и товарным знакам (№ регистрации 2006612482 и 2006612481 соответственно).

Апробация работы. Основные положения диссертационной работы и вопросы их практического использования докладывались и обсуждались на 8 международных и всероссийских конференциях, семинарах, основными из которых являются: Международная научно-техническая конференция и Российская научная школа молодых ученых и специалистов «Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий» (Сочи, 2001); IV всероссийская научная конференция с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2001); Международная конференция и Российская научная школа «Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий» (Москва, 2002); V всероссийская научная конференция с международным участием молодых ученых и аспирантов «Новые информационные технологии, Разработка и аспекты применения» (Таганрог, 2002); V конференция молодых ученых, (Нальчик, 2004); И Всероссийская конференция «Проблемы информатизации регионального управления» (Нальчик, 2006); II Международная конференция «Моделирование устойчивого регионального развития» (Нальчик, 2007).

Публикации. По результатам диссертационной работы опубликовано 14 работ, в том числе 8 статей, из них одна статья в научных изданиях из перечня ВАК и 2 зарегистрированные программы. Без соавторов опубликовано 6 работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и 8 приложений. Работа изложена на 157 страницах основного текста, содержит 46 рисунков, 30 таблиц, 9 страниц списка использованных источников, состоящего из 92 наименований. В приложениях приведены акты об использовании и внедрении результатов диссертации, свидетельства о регистрации программ для ЭВМ.

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

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

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

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

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

^YJ,=r^=c;^>lrf7-^>1r^ 0)

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

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

/Ч4 = и>л4 = 2;>/У4= з;>....

2) вероятность ошибок кратности г зависит от значения вероятности искажения одного символа слова -р\\\ общего числа символов в слове - п.

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

модель ДСК Показано, что совместное воздействие на

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

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

Таблица 1 - Значения вероятностей ошибок кратности г - Р(ёе = г) в 16-и разрядных словах, соответствующие десятикратному изменению р\

Р! 0,001 0,01 Увеличение в (Т) Уменьшение в (1)

Р(с1,,=0) 0,984 0,851 4- в 1,2 раза

0,015 0,137 Т в 9,13 раза

0,0001 0,0104 Т в 104 раза

Р(с1,,=3) 0,00000055 0,000491 Т в 892,7 раза

Анализ полученных результатов позволяет заключить, что с ростом вероятности искажения одного разряда р{ происходит перераспределение вероятностей ошибок различной кратности - вероятность получения неискаженного слова - Р(с1с = 0) уменьшается, а вероятности искажения слов одной и тем более двумя или тремя ошибками - увеличиваются.

Одна из особенностей современных АСОИиУ - увеличение объемов обрабатываемой ими информации, что достигается как увеличением числа передаваемых и хранимых слов, так и их разрядности - п. Показано, что наращивание разрядности слов сопровождается аналогичным, как и при росте р|, но менее выраженным эффектом перераспределения значений Р(с1с = г) - вероятность отсутствия ошибок уменьшается, а вероятности ошибок кратности с!с = 1,2,3,... - увеличиваются.

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

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

N 1 1

ла и ограничено значением г| = < —, где Л^ = 2 -1 - число исправляемых кодом ошибок, а N = 2" -1 - общее число возможных ошибок.

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

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

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

Исходным данным является число информационных символов (от), а исходными требованиями - кратности обнаруживаемых (d„) и исправляемых (d„) ошибок.

Показано, что построение производящей матрицы кода G = \l\B\ может быть обеспечено путем программной генерации ¿-разрядных слов -строк подматрицы В свесами u>(B,)>d-l (общее число таких слов равно:

N[u(B, )>d-l]~ + Cdk + Cf +.... + С»'"1 + C[ , и последующего отбора из них т слов, попарно отстоящих не менее чем в (d ~ 2) разрядах:

disi(B,,B )> d-2 для всех /s/Sm, /<j<m,(i*j).

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

На заключительном этапе процесса построения корректирующего кода проводят проверку достоверности декодирования. Для однозначного определения как кратности ошибок, так и их месторасположения в кодовых словах и, следовательно, возможности их достоверного декодирования каждой возможной комбинации ошибок, исправляемых кодом, должно соответствовать свое оригинальное значение синдрома S(d„). С тем, чтобы уменьшить риск ложного декодирования алгоритму декодирования обычно придают возможность обнаружения в словах ошибок кратности d„ > du (как правило, d„ = d„ + 1). Для этого необходимо, чтобы значения синдромов ошибок кратности d„ - S(d0) отличались от нуля и не совпадали со значениями синдромов исправляемых кодом

ошибок S(d„). В то же время различным комбинациям ошибок кратности d„ > d„ могут соответствовать совпадающие значения синдромов.

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

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

Таблица 2 - Словарь ошибок для кода (п. т)

Кратность ошибок Искаженные символы кодового слова ах ... а, ... ат ц ... а, ... ^ Значение синдрома s, ... se ... sk

0 0 ... 0 ... 0

1 1 * » 1 ... 1 ... 0 0 ... 1 ... 1

2 * « 0 ... 1 ... 0

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

Таблица 3 - Основные параметры кода, исправляющего ¿/„ и обнаруживающего d„ ошибок

d,„ d„ d„ = 2 d„ = 2, d„ = 3 d„ = 3

m 4 8 16 4 8 16 4 8

^min 6 7 9 6 7 9 9 9

к 7 8 10 8 9 11 10 11

n 11 16 26 12 17 27 14 19

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

)Ш ГП) /77|

/ 1 \

I 1 ... I | ... | I I ■■■ I

тI - ■ ■ ») ■ • Н— т,----Ч-»—■ Н —■- н* • £ -Н

Рисунок 2 - Схема деления т-разрядного информационного слова на слоги и их автономного кодирования

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

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

я

В результате получаем кодовое слово, содержащее п-^п, символов, да

а

которых /л = ]Г/л, - информационные (при условии деления слова на непере-

ы

а

секаюшиеся слоги) и проверочные.

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

г

лами кодового слова равно: М11(с1е = г) = Х\Сщ > где ГТ ~ знак опеРаиии

умножения. В то же время общее число возможных вариантов распределения г ошибок между п символами кодового слова равно: ЛУс1е =г)~С'п > Ыи(г/. = г) и, следовательно, вероятность исправления многократных (¿4 = г) ошибок

N ((1 = г)

определяется выражением: Р1(с(е=г) = —-—--= —-.

М(с1с=г) С'„

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

1) числа слогов £ и их разрядности

2) корректирующего кода для кодирования слогов.

Решение этих вопросов должно быть найдено из анализа следующих, в общем случае, противоречивых условий:

- обеспечение требуемых корректирующих возможностей и приемлемой достоверности декодирования;

- простоты реализации процедур кодирования и в особенности декодирования.

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

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

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

ад=э

1 0,8 0,6 0,4 0,2 0

а)

/ч/ о 1 1

0,8 0,6 О А 0,2 0

I

И

I»"

5 6

б)

7 8

Рисунок 3 - Интервалы изменения вероятности исправления двойных ошибок при делении информационных слов разрядности 8 (а) и 16 (б) на слоги, для кодирования которых применен код Хэмминга

16

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

Таблица 4 - Варианты деления 8-и разрядного слова на 3 слога и соответствующие им значения вероятностей исправления двойных ошибок

№ варианта I 2 3 4 5

т, 1 1 1 2 2

т2 1 2 3 2 3

тг 6 5 4 4 3

РМ = 2) 0,5 0,639 0,675 0,698 0,705

4. Приоритет при выборе кода, используемого для кодирования слогов, следует отдать удлиненному коду Хэмминга, как обеспечивающему более высокую нежели код Хэмминга достоверность декодирования - вероятность ложного декодирования исключается для двойных ошибок и существенно снижается для ошибок кратности с!е > 3.

Проведен сопоставительный анализ корректирующих возможностей и сложности реализации кодов, исправляющих многократные ошибки: построенного с применением регулярного метода и альтернативных кодов, полученных делением исходного слова на слоги и их последующего кодирования с помощью кодов Хэмминга. Для сравнения выбраны код(16,8) с (1 = 5 и, следовательно, исправляющий все ошибки кратности ёе < 2 (1-я строка табл. 5) и коды, полученные делением 8-и разрядного слова на два, три и четыре слога, каждый из которых кодируется кодом Хэмминга (2, 3, и 4 строки табл. 5).

Таблица 5 - Корректирующие возможности сравниваемых кодов и оценки сложности их декодирования

1

Число/процент исправляемых ошибок кратности Общее число Слож ность декодирования 1

№ Код 1 2 3 4 исправляемых ошибок

1 (16,8) 16/100 120/100 - - 136 292

2 (14,8)=(7,4)+(7,4) 14/100 49/54 - - 63 38

3 (17,8)=(6,3)+ +(6,3)+(5,2) 17/100 96/70,5 180/26,5 - 293 41

4 (20,8)= (5,2)+ (5,2)+(5,2)+ (5,2) 20/100 150/78,9 500/43,8 625/12,9 1295 44

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

ыо

где £„„,,„„, и Ь<)сш - сложности схем вычисления синдрома и дешифрации синдрома. Выражение (2) не содержит оценки сложности схемы корректора Ь , как совпадающей для сравниваемых кодов. Действительно, так как в

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

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

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

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

Проведена сравнительная характеристика двумерных ИК для выбора типов кодов, составляющих ИК. Доказано, что ИК с комбинацией удлиненного кода Хэмминга и кода с проверкой на четность является наиболее оптимальным решением для защиты данных от многократных ошибок. Предложенный двумерный ИК характеризуется кодовым расстоянием ¿=8и, следовательно, позволяет исправить до трех ошибок вне зависимости от их местоположения в таблице и причин появления.

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

Информационное |-1-1-]-1

слово (a j K'l •■•

Кодирующая программа

Кодер j }E

Кодовое слово (A„) |o„,| . . . ' i [ y^ ... 1 .

Адресуемой ЯП

Контрольная строка

M ... Г I

I I ... I

Контрольная строка

До записи А„ После записи А„

Рисунок 4 - Алгоритм кодирование двумерным итеративным кодом с с) = 8

Функция кодирования задается как £ = £, ° £,. При этом £, (где £,=£,,£,,■■•£,) есть операция кодирования всех информационных слов т,. ш,.....т с помощью удлиненного кода Хэмминга, а £2 операция кодирования столбцов таблицы по модулю два

\

(3)

где о - информационные символы, при этом = • •• о,„ .

Тогда выражение 7" ° £ для определения влияния функции ошибок Г, с вероятностью р на функции £:

aid m ^

Т°Е = Т°ЕгоЕ,=Тсг^Е2 (^ЦЕ,/^,,)))

h = 1 V i = l

(4)

/л

где Т = Тсг о Т, ; Гсг - функция ошибки, с вероятностью рсг влияющая на контрольную строку с^есД: row fcrj, 7]- функция ошибки, с вероятностью р,

влияющая на

Получена модель двумерного ИК, которая может быть выражена следующим образом:

, ( ч "Л

F(m)= DoToE(m)=D2(Tcr^E, (^Оиа(Еч(^а„)))) ), (5)

I Л

ч

где D = D2 ° D,, D, = Функция декодирования удлиненного кода

Хэмминга, Dj- функция декодирования кода с контролем четности.

Если А - информационное слово, состоящее из М информационных символов (где М = m-q), то схема кодирования определяется следующими

формулами

Е( А ) = Е( аиап ■■■ а,т), Е( агхагг---а1т ),■■■ -•£( аЧ1ая2''' ),E(auair--a4J,E( апап -ач1),-.Е( аыа1т ■ ■ ■ а1/т ), (6)

где Е( -alm) = ••■amaIJ-alt. где k = \+[log2—].

Я

Формируются контрольная строка: E(alfa ■■■av) = ana)tSj •••ач,Р;,

ч

0. если mod 2 а ц - четная ;

где

Р,

если ]Г mod 2 о|( -

При этом каждому из п (п = т + к) разрядов присваивается слева направо номер от 1 до п. Для заданного слова а0я ■■■ат составляются контрольные суммы а,у ■■■а,к по модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем: для а,у (I < ¡<к ) выбираются разряды, содержащие биты исходного слова, двоичные числа-номера которых имеют в у'-м разряде единицу.

Алгоритм декодирования двумерного ИК определяется следующими формулами:

0(Аап-а^г-Рт)= 0(аиа12 ■■■ ачт а,, ••• а^р, ••■ р„,; =

= 0(а,,а13 ■ • •а,.,«,,. ■ • ■«„ ),0(а21а22 ■ ■ •а2„,а2/ ■ • -а2к а„о^ • ■ -а</т• • .а,,),

аиа2, ••• 0(апа22 ••• а?2Р2 ),■■■ а,„,а2„, ••• а1/тр„, ). (7)

Обозначим через 5,( сумму по модулю 2 разрядов, слова я,у.а,у,| •••а1т , соответствующих контрольной сумме а,(, и самой этой контрольной суммы.

<н

При этом 5, = • Если =0 и ^mod2 ац -четная, то

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

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

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

Рисунок 5 - Интерфейс подпрограммы Data decoding speed

Формируется задача условной минимизации избыточности кода для эффективного осуществления передачи данных. Параметрами оптимизационной задачи являются число информационных символов и неравенство Хэмминга. С помощью разработанной подпрограммы 2D-Q найдены значения q, которые определяют минимум избыточности при М=\6, 32, 64 и 128. Выбор q и m (q ■ т = М ) ИК с d= 8 для заданного Мосуществляется из условия обеспечения:

K=(q+\){ 1 + %2— )+ —= <7+1 + q.log2 — +—. (8)

Я Я ' Я Я

!__i_ м_

К = Ктт при q = M- 2 '"2 «\

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

Проведено сравнение двумерного ИК с кодом (19,8), построенным с применением регулярного метода. Установлено, что предложенный код обладает низкой сложностью декодирования (I = 102) по сравнения с кодом (19,8) исправляющим также до трех ошибок. Корректирующие возможности и параметры кода (19,8), построенного с применением регулярного метода и двумерного итеративного кода сЛ = $ид = 2 приведены в табл. 6.

Таблица 6 - Корректирующие возможности и параметры кода (19,8), построенного с применением регулярного метода и двумерного итеративного кода сс/=8и<7 = 2

№ Код Кодовое расстояние а Число исправляемых ошибок Число обнаруживаемых ошибок Информационная . избыточность Я Эффективность кодирования ЕР Сложность декодирования Ь

1 (19.8) 7 3 3 2,38 0,73 989

2 (24.8) 8 3 4 3 0,5 102

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

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

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

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

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

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

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

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

- модель и метод, основанные на кодировании данных, защищенных двумерным итеративным кодом.

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

6. Результаты диссертационной работы внедрены в учебный процесс Кабардино-Балкарского государственного университета:

- на кафедре автоматизированных систем обработки информации;

- на факультете микроэлектроники и компьютерных технологий.

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

1. Тугуж У.Х. Метод коррекции многократных ошибок в каналах передачи и хранения, основанный на делении слов данных на слоги и их автономном кодировании / У.Х. Тугуж, Ю.К. Тлостанов // Нелинейный мир. -2007. - Т. 5, № 6. - С. 390-396. (Личный вклад Тугуж У.Х. - Проведение вычислительного эксперимента, обработка экспериментальных результатов, обсуждение и теоретическое обоснование полученных результатов).

2. Тугуж У.Х. Метод коррекции многобитовых ошибок в запоминающих устройствах / Ю.К. Тлостанов, У.Х. Тугуж // Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий: Материалы международной конференции и Российской научной школы. - М.: МГИЭМ, 2001. - Ч. 3. - С. 94. (Личный вклад Тугуж У.Х. - Описание практической реализации предлагаемого метода).

3. Тугуж, У.Х. К вопросу проектирования оперативных запоминающих устройств, защищенных от многобитовых ошибок / Ю.К. Тлостанов, У.Х. Тугуж // Новые информационные технологии. Разработка и аспекты применения: Тезисы докладов IV всероссийской научной конференции с международным участием молодых ученых и аспирантов. - Таганрог: ТРТУ, 2001- С. 56-57. (Личный вклад Тугуж У.Х. - Предложен и обоснован рациональный вариант комбинации кодов, составляющих итеративный код).

4. Тугуж У.Х. Метод обнаружения и исправления ошибок в оперативных запоминающих устройствах, основанный на делении слов памяти на слоги / Ю.К. Тлостанов, У.Х. Тугуж // Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий: Материалы международной конференции и Российской научной школы. - М.: Радио и связь, 2002. - Кн. 3. - Ч. 8,- С. 47-49. (Личный вклад Тугуж У.Х. - Оценены значения вероятностей обнаружения и коррекции двойных и тройных ошибок в словах памяти при их делении на слоги, сделаны выводы на основании полученных результатов).

5. Тугуж, У.Х. К вопросу проектирования итеративного кода / У.Х. Тугуж // Новые информационные технологии. Разработка и аспекты применения: Тезисы докладов V всероссийской научной конференции молодых ученых и аспирантов. - Таганрог: ТРТУ, 2002.- С. 116-118.

6. Тугуж У.Х. Повышение обнаруживающих и корректирующих возможностей путем деления слов памяти (DRAM) на слоги / У.Х. Тугуж // III Конференция молодых ученых: Сборник научных трудов - Нальчик: КБНЦ РАН, 2002,-С. 35-37.

7. Тугуж У.Х. Выбор мерности итеративного кода, проверка на четность / У.Х. Тугуж // III Конференция молодых ученых: Сборник научных трудов. - Нальчик: КБНЦ РАН, 2002,- С. 37-40.

8. Тугуж У.Х. Обоснование выбора типов кодов составляющих итеративного кода для коррекции ошибок в ОЗУ / У.Х. Тугуж // IV Конференция молодых ученых: Тезисы докладов. - Нальчик: КБНЦ РАН, 2003. - С. 19-20.

9. Тугуж У.Х. Метод повышения надежности ОЗУ, основанный на делении слов памяти на слоги / У.Х. Тугуж // V Конференция молодых ученых: Тезисы докладов. - Нальчик: КБНЦ РАН, 2004. - С. 41-43.

10. Тугуж У.Х. Алгоритм и программа коррекции ошибок в данных, представленных двумерной таблицей / Ю.К. Тлостанов, У.Х. Тугуж // Проблемы информатизации регионального управления: Материалы II Всероссийской конференции. - Нальчик: КБНЦ РАН, 2006. - С. 175-178. (Личный вклад Тугуж У.Х. - Разработал алгоритм и составил программу).

11. Тугуж У.Х. Алгоритм формирования модели кода, обнаруживающего и корректирующего заданное число ошибок / У.Х. Тугуж, Ю.К. Тлостанов // МИТС-НАУКА. Международный научный вестник: Сетевое электронное научное издание - Ростов-на-Дону: РГУ, 2006. - № 4; Иден. номер 0420600032\0043 (Личный вклад Тугуж У.Х. - Разработал алгоритм и составил программу).

12. Тугуж У.Х. Программа, моделирующая процессы обнаружения и коррекции многократных ошибок в данных, защищенных двумерным итеративным кодом / У.Х. Тугуж // Моделирование устойчивого регионального развития: Материалы II международной конференции. - Нальчик: КБНЦ РАН, 2007.-Т. 3.-С. 116-123.

СВИДЕТЕЛЬСТВА ОБ ОФИЦИАЛЬНОЙ РЕГИСТРАЦИИ ПРОГРАММ ДЛЯ ЭВМ

13. Тугуж У.Х. Алгоритм и программа обнаружения и коррекции многоразрядных ошибок в данных, защищенных двумерным итеративным кодом: Свидетельство о регистрации программ для ЭВМ № 2006612481 / У.Х. Тугуж, Ю.К. Тлостанов, И.Б. Байрактаров // заявитель и правообладатель «Кабардино-Балкарский государственный университет». -№ 2006611930; заявл. 13.06.06.; зарег. 12.07.06. в Реестре программ для ЭВМ - М.: Федеральная служба по интеллектуальной собственности, патентам и товарным знакам.

14. Тугуж У.Х. Программа формирования модели корректирующего кода с заданным кодовым расстоянием: Свидетельство о регистрации программ для ЭВМ № 2006612482 / У.Х. Тугуж, Ю.К. Тлостанов, Л.А. Мусуко-ва // заявитель и правообладатель «Кабардино-Балкарский государственный университет». - №-2006611931; заявл. 13.06.06.; зарег. 12.07.06. в Реестре программ для ЭВМ - М.: Федеральная служба по интеллектуальной собственности, патентам и товарным знакам.

В печать 13.10.20087. Тираж 100 экз. Заказ № 5541. Полиграфический участок ИПЦ КБГУ 360004, г. Нальчик, ул. Чернышевского, 173.

Введние.

Глава 1. Проблема обеспечения надежности и достоверности передачи и хранения данных.

1.1. Организация передачи и хранения данных. Модели каналов передачи и хранения данных.

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

1.2.1. Причины возникновения ошибок в каналах передачи и хранения данных.

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

1.2.3. Причины ограниченного применения кодов, корректирующих многократные ошибки.

1.3. Пути повышения надежности передачи и хранения данных.

Выводы по главе 1.

Глава 2. Построение модели кода, обнаруживающего и корректирующего многократные ошибки.

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

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

Выводы по главе 2.

Глава 3. Метод обнаружения и коррекции многократных ошибок, основанный на делении слов на слоги и их автономном кодировании — декодировании.

3.1. Содержание метода.

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

3.2.1. Анализ возможных способов деления слов на слоги и критерии выбора оптимального.

3.2.2. Критерии выбора корректирующего кода, применяемого для защиты слогов.

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

Выводы по главе 3.

Глава 4. Модель и метод обнаружения и коррекции многократных ошибок в данных, защищенных двумерным итеративным кодом.

4.1. Итеративные коды, основные понятия и определения.

4.2. Обоснование выбора и оптимизация параметров ИК.

4.2.1. Обоснование выбора мерности ИК.

4.2.2. Обоснование выбора типов кодов, составляющих ИК.

4.2.3. Обоснование выбора мерности сегмента таблично представленных данных.

4.3. Алгоритмы кодирования и декодирования данных.

4.4 Модель двумерного ИК; оптимизация параметров модели.

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

Выводы по главе 4.

Актуальность темы. Интенсивное развитие информационных технологий и широкое внедрение реализующих их автоматизированных систем обработки информации и управления (АСОИиУ) практически во все сферы человеческой деятельности, увеличение объемов и сложности осуществляемых ими преобразований информации требуют обеспечения соответствующего целевому применению систем уровня их надежности и достоверности выполняемых преобразований. Особую остроту вопросы обеспечения и поддержания высокого уровня надежности и достоверности функционирования приобретают для систем управления особо ответственными объектами и процессами — систем критических приложений (энергетика, транспорт, экология, оборона и т.д.), для которых ошибки в функционировании могут привести к тяжелым или катастрофическим последствиям [46, 74].

Повышение надежности АСОИиУ и достоверности их функционирования может быть достигнуто различными методами. Исследования по данной проблематике привели к возникновению нового направления — синтеза систем, толерантных к возможным отказам и сбоям или отказоустойчивых систем [9, 24].

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

Опыт эксплуатации АСОИиУ свидетельствует о том, что наиболее подверженными влиянию причин возникновения ошибок являются каналы передачи данных и запоминающие устройства (каналы хранения данных), для которых самым адекватным аппаратом обеспечения их отказоустойчивости и, следовательно, достоверности функционирования является помехоустойчивое кодирование данных [8, 22, 34].

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

В то же время практика вплотную подошла к более высокому уровню требований по надежности и достоверности передачи и хранения данных [4] — необходимости исправления в данных двух, трех, а в ряде случаев и большей кратности ошибок [74, 89].

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

Объектом исследования являются дискретные каналы передачи и хранения данных АСОИиУ.

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

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

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

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

- проведение анализа существующих методов и средств кодовой защиты в каналах передачи и хранения данных;

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

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

- анализ причин, ограничивающих широкомасштабное применение кодов, исправляющих многократные ошибки, в их чистом виде;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1. Метод, основанный на делении слов на слоги и их автономного кодирования с помощью простых корректирующих кодов.

3.2. Модель и метод, основанные на кодировании данных с помощью итеративныхкодов.

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

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

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

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

- Международная научно-техническая конференция и Российская научная школа молодых ученых и специалистов «Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий» (Сочи, 2001);

- IV всероссийская научная конференция с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2001);

- Международная конференция и Российская научная школа «Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий» (Москва, 2002);

- V всероссийская научная конференция с международным участием молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2002);

- V конференция молодых ученых, (Нальчик, 2004);

- II Всероссийская конференция «Проблемы информатизации регионального управления» (Нальчик, 2006);

- II Международная конференция «Моделирование устойчивого регионального развития», (Нальчик, 2007).

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

- на кафедре автоматизированных систем обработки информации;

- на факультете микроэлектроники и компьютерных технологий. Публикации. По результатам диссертационной работы опубликовано 14 работ, в том числе 8 статей, из них одна статья в научных изданиях из перечня ВАК и 2 зарегистрированные программы. Без соавторов опубликовано 6 работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и 8 приложений. Работа изложена на 157 страницах основного текста, содержит 46 рисунков, 30 таблиц, 9 страниц списка использованных источников, состоящего из 92 наименований. В приложениях приведены акты об использовании и внедрении результатов диссертации, свидетельства о регистрации программ для ЭВМ.

Выводы по главе 4.

1. Рассмотрен общий подход применения ИК исходя из требования к его обнаруживающим и корректирующим возможностям.

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

3. Получен двумерный ИК, обладающий весьма сильной корректирующей способностью и характеризующийся минимальным кодовым расстоянием равным восьми и который позволяет обнаружить до четырех и исправить до трех ошибок вне зависимости от их местоположения в таблице и причин появления. Установлено, что кратность исправляемых ошибок существенно увеличивается в следующих случаях: 1) ошибки нечетной кратности сосредоточены в пределах одной строки или столбца, 2) ошибками произвольной, но нечетной кратности искажена одна из строк, а каждая из остальных строк таблицы содержит не более одной ошибки, обусловленной сбоем.

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

5. Предложены алгоритмы, реализующие процедуры кодирования и декодирования для обнаружения и коррекция многократных ошибок в данных защищенных двумерным ИК.

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

7. Проведено сравнение предложенного нами двумерного ИК и классической модели кода(26,16), построенного с применением регулярного метода. Установлено, что разработанный код эффективнее по корректирующей возможности и по эффективности кодирования, имеет относительно низкую сложность алгоритмической реализации и может быть рекомендован для оптических волоконных каналов, где большинство возникающих ошибок в условиях эксплуатации распределяется в пределах de=l (66%) и de=2, de=3 (23%).

147

Заключение

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

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

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

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

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

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

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

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

- модель и метод, основанные на кодировании данных, защищенных двумерным итеративным кодом.

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

6. Результаты диссертационной работы внедрены в учебный процесс Кабар-дино - Балкарского государственного университета:

- на кафедре автоматизированных систем обработки информации;

- на факультете микроэлектроники и компьютерных технологий.

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

149

1. Амелькин, В.А. Методы нумерационного кодирования / В.А Амелькин. -Новосибирск: Наука, 1986,-155 с.

2. Артамонов, А.А. Передающее оборудование для цифрового телевещания / А.А. Артамонов, JI.H. Протопопов // Электроника: НТБ, 2007. № 8. — С. 44-48.

3. Архипкин, А.В. Турбокоды мощные алгоритмы для современных систем связи / А.В. Архипкин // Беспроводные технологии, 2006. - № 1. — С. 36-38.

4. Архипкин, В.Я. Сравнительная помехозащищенность систем связи с широкополосными и узкополосными сигналами / В.Я.Архипкин, К.А. Меш-ковский // Информация и космос, 2004. № 3. - С. 23-27.

5. Балашов, Е.П. Запоминающие устройства повышенной надежности / Е.П. Балашов, Б.Ф. Лаврентьев, А.О. Тимофеев, Л.А. Шумилов. Л.: Энергия, Ленинградское отделение, 1978. —200 с.

6. Баринов, В.В. Сверхбольшие интегральные микросхемы оперативных запоминающих устройств / В.В. Баринов, А.С. Березин, В.Д. Вернер и др. — М.: Радио и связь, 1990. -272 с.

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

8. Блейхут, Р.Э. Быстрые алгоритмы цифровой обработки сигналов / Р.Э. Блейхут. Пер. с англ.- М.: Мир, 1989, -448 с.

9. Ю.Блох, Э.Л. Модели источника ошибок в каналах передачи цифровой информации / Э.Л. Блох, О.В. Попов, В.Я. Турин. — М.: Связь, 1971. — 312 с.

10. П.Богданов, В.Н. Защита от ошибок в сетях ATM / В.Н. Богданов, П.С. Вих-лянцев, М.В. Симонов // Информост, 2002, -№3, -С. 20-24.

11. Борисов, B.C. Обнаружение и исправление ошибок в запоминающих устройствах / B.C. Борисов // Зарубежная радиоэлектроника. 1984. -№ Ю,— С. 24-44.

12. Боровков, А.А. Теория вероятностей: Учеб. пособие для вузов / А.А. Боровков М.: Наука, 1986. -432с.

13. Бояринов, И.М. Исправление ошибок в основной памяти высокопроизводительных ЭВМ / И.М. Бояринов, А.А. Давыдов, Б.М. Шабанов // Автоматика и телемеханика, 1987. №7. -С. 152-165.

14. Бродски, М. Уменьшение частоты случайных сбоев, вызываемых в динамических ЗУПВ действием а -частиц / М. Бродски // Электроника. 1980. — №10.-С. 69-80.

15. Бурляев, И.А. Эксплуатация и ремонт ЭВМ, организация работы вычислительного центра / И.А. Бурляев, И.А. Орлов, В.Ф. Корнюшко. М.: Энергоатомиздат, 1989. -400 с.

16. Васильев, В.И. Графы кодов, устройства и сети передачи сигналов данных / В.И. Васильев, В.М. Коновалов, Л.Я. Заманский. М.: Радио и связь, 1985. -199 с.

17. Верниковский, Е.А. БИС обнаружения и исправления ошибок для систем памяти / Е.А. Берниковский, В.К. Конопелько, В.В. Лосев, А.И. Сухопа-ров // Зарубежная электронная техника, 1983. — Т.7. — С. 3-32.

18. Гобчанский, О.П. Применение MicroPC в вычислительных комплексах специального назначения / О.П. Гобчанский // Современные технологии автоматизации, 1997. — № 1. С. 38-41.

19. Гобчанский, О.П. Проблемы создания бортовых вычислительных комплексов малых космических аппаратов / О.П. Гобчанский // Современные технологии автоматизации, 2001. — № 4. — С. 28-34.

20. Горшков, В.Н. Надежность оперативных запоминающих устройств ЭВМ / В.Н. Горшков. Л.: Энергоатомиздат, 1987. —168 с.

21. Гук, М. Аппаратные средства IBM PC: Энциклопедия / М. Гук. СПБ.: Питер, 2001.-816 с.

22. Гуляев, В.А. Контроль ЭВМ / В.А. Гуляев. Киев: Наукова думка, 1977. -168 с.

23. Деундяк, В.М. Имитационная модель цифрового канала передачи данных и алгебраические методы помехоустойчивого кодирования / В.М. Деун-дяк, Н.С. Могилевская // Вестник ДГТУ, том 1, N 1(7). Ростов н/Д: ДГТУ, 2001. С. 98-104.

24. Золотарев, В.В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник / В.В. Золотарев, Г.В. Овечкин. — М.: Горячая линия — Телеком, 2004. -126 с.

25. Золотарев, В.В. Эффективные алгоритмы помехоустойчивого кодирования для цифровых систем связи / В.В. Золотарев, Г.В. Овечкин // Электросвязь. 2003.- № 9. С. 34-37.

26. Ивахненко, А.Г. Помехоустойчивость моделирования / А.Г. Ивахненко, B.C. Степашко. — Киев: Наук, думка, 1985. 216 с.

27. Иыуду, К.А. Надежность, контроль и диагностика вычислительных машин и систем / К.А. Иыуду. М.: Высшая школа, 1989. -216 с.

28. Каган, Б.М. Основы эксплуатации ЭВМ / Б.М. Каган, И.Б. Мкртумян. -М.: Энергоатомиздат, 1988. -432 с.

29. Лебедев, О.Н. Микросхемы памяти и их применение / О.Н. Лебедев. — М.: Радио и связь, 1990. —160 с.

30. Левин, Б.Р. Вероятностные модели и методы в системах связи и управления / Б.Р. Левин, В. Шварц. — М.: Радио и связь, 1985. —312 с.

31. Лидовский, В.В. Теория информации: Учебное пособие / В.В. Лидовский.

32. М.: Компания спутник +, 2004. —111с.

33. Майоров, С.А. Введение в микроЭВМ / С.А. Майоров, В.В. Кириллов, А.А. Приблуда. Л.: Машиностроение, 1988. -303 с.

34. Максимей, И.В. Имитационное моделирование на ЭВМ / И.В. Максимей.- М.: Радио и связь, 1988. 232 с.

35. Мак-Элис, Р. Дж. Надежность памяти ЭВМ. Современный компьютер. Сборник популярных статей / Р. Дж. Мак-Элис. — М.: Мир, 1986 — С. 203209.

36. Малев, В.А. Структурная избыточность в логических устройствах / В.А. Малев.-М.: Связь, 1978.-С. 12-14.

37. Марков, А.А. Моделирование информационно-вычислительных процессов / А.А. Марков. М.: Изд-во МГТУ им. Н.Э. Баумана, 1999. - 360 с.

38. Никулин, B.C. Диагностика и коррекция ошибок в полупроводниковых запоминающих устройствах / B.C. Никулин, B.C. Борисов, В.В. Горемы-кин. Кишинев, Штиинца, 1987. —137 с.

39. Огнев, И.В. Надежность запоминающих устройств / И.В. Огнев, К.Ф. Са-рычев. — М.: Радио и связь, 1988. —233 с.

40. Питерсон, У.У. Коды, исправляющие ошибки / У.У. Питерсон. Пер. с англ. М.: Мир, 1976. -594 с.

41. Попов, В.Д. Проблемы и возможности применения коммерческих интегральных схем в военной и космической технике / В.Д. Попов // Chip News. — 1999. № 5.- С. 28-32.

42. Потемкин, И.С. Функциональные узлы цифровой автоматики / И.С. Потемкин. — М.: Энергоатомиздат, 1988. —319 с.

43. Сагалович, Ю.Л. Кодовая защита оперативной памяти ЭВМ от ошибок / Ю.Л. Сагалович // Автоматика и телемеханика, 1991. —№5 — С. 3-37

44. Самофалов, К.Г. Структурно-логическиие методы повышения надежности запоминающих устройств / К.Г. Самофалов, В.И. Корнейчук, А.В. Го-родний. — М.: Машиностроение, 1976. —112 с.

45. Сарторе, Р.Г. Применение кода Файра для обнаружения и исправления ошибок в многоразрядных ЗУПВ большой емкости / Р.Г. Сарторе, Д.У. Галли // Электроника, 1982.- №2. С. 54-59.

46. Смирнов, Ю.М. Полупроводниковые запоминающие устройства / Ю.М. Смирнов. М.: Высшая школа, 1989. -160 с.

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

48. Толстякова, B.C. Обнаружение и исправление ошибок в дискретных устройствах / B.C. Толстякова. —М.: Советское радио, 1972.

49. Тугуж, У.Х. Выбор мерности итеративного кода, проверка на четность / У.Х. Тугуж // Сборник научных трудов. III конференция молодых ученых25.27 сентября 2002). В 2-х частях. Часть 1. -Нальчик: Издательство КБНЦ РАН, 2002. С. 37-40.

50. Тугуж, У.Х. Обоснование выбора типов кодов составляющих итеративного кода для коррекции ошибок в ОЗУ / У.Х. Тугуж // IV Конференция молодых ученых. Тез. докл. — Нальчик: КБНЦ РАН, 2003. С. 19-20.

51. Тугуж, У.Х. Метод коррекции многократных ошибок в каналах передачи и хранения, основанный на делении слов данных на слоги и их автономном кодировании / У.Х. Тугуж, Ю.К. Тлостанов // Нелинейный мир, 2007. -№ 6. Т.5. -С. 390-396.

52. Фомичев, С.М. Обзор математических моделей каналов связи и их применение в телекоммуникационных системах / С.М. Фомичев, А.В. Аби-лов. Ижевск: ИГТУ, 2001. 60 с.

53. Хетагуров, Я.А. Повышение надежности цифровых устройств методами избыточного кодирования / Я.А. Хетагуров, Ю.П. Руднев. —М.: Энергия, 1974.-272 с.

54. Хиндин, X. Дж. Контроль и исправление ошибок в многоразрядных устройствах памяти / X. Дж. Хиндин // Электроника, 1982 — №11. С.52-53.

55. Хэмминг, Р.В. Теория кодирования и теория информации / Р.В. Хэмминг. М.: Радио и связь, 1983.- 176 с.

56. Цымбал, В.П. Теория информации и кодирования / В.П. Цымбал. — Киев: Головное издательство издательского объединения "Вища щкола", 1977. -288 с.

57. Шевкопляс, Б.В. Микропроцессорные структуры. Инженерные решения / Б.В. Шевкопляс. -М.: Радио и связь, 1986. -264 с.

58. Шеннон, К. Математическая теория связи / К. Шеннон // Сборник «Работы по теории информации и кибернетике». — М.: ИИЛ, 1963. —244 с.

59. Шинаков, Ю.С. Теория передачи сигналов электросвязи / Ю.С. Шинаков, Ю.М. Колодяжный. М.: Радио и связь, 1989. -288 с.

60. Штагер, В.В. Цифровые системы связи. Теория расчет и оптимизация / В.В. Штагер. М.: Радио и связь, 1993. -312 с.

61. Щербаков, Н.С. Самокорректирующиеся дискретные устройства / Н.С. Щербаков. -М.: Машиностроение, 1974. -214 с.

62. Эванс, М. Матрица Нельсона, позволяющая исправить две ошибки на слово / М. Эванс // Электроника, 1982 №1.- С. 59-66.

63. Юдиницев, В.В. Радиационно стойкие интегральные схемы, надежность в космосе и на земле / В.В. Юдиницев // Электроника: НТБ, 2007. — №5. — С. 72-77.

64. Cataldo, A. IBM moves to protect DRAM from cosmic invaders / A. Cataldo. EE times online edition, FISHKILL, N.Y., USA, 1998. pp. 1-3.

65. Dodd, P. E. Impact of Technology Trends on SEU is CMOS SRAMs / P. E. Dodd, F. W Sexton., G. L. Hash // IEEE Transactions on Nuclear Science, December 1996,-V. 43-N. 6,-pp. 2797-2804.

66. Jae-Yoon, S. A CMOS Transceiver for DRAM Bus System With a Demultiplexed Equalization Scheme / S. Jae-Yoon, N. Jang-Jin, S. Young-Soo // IEEE journal of solid-state circuits, February 2002 Vol. 37 — Issue 2 — pp. 243-250.

67. Jin, H. Irregular repeat-accumulate codes / H. Jin, A. Khandekar, R. McEliece // Proc. 2nd Int. Symp. on Turbo Codes and Related Topics, Brest, France, Sept. 2000.-pp. 1-8.

68. Jones, M. E. "When Memories Forget" Soft errors in very deep sub-micron memories / M. E. Jones. MoSys, Inc. Sunnyvale, CA, USA, 2001 pp. 3-9.

69. Joohee, K. Dynamic Memory Design for Low Data-Retention Power / K. Joo-hee, C. Marios // Department of Electrical Engineering and Computer Science. University of Michigan, Ann Arbor, USA, 2001 pp. 207-216.

70. Lage, C. Soft Error Rate and Stored Charge Requirements in Advanced High-Density SRAMs / C. Lage, D. Burnett,, T. McNelly // 1993 IEEE International Electron Devices Meeting, 1993-pp. 821-824.

71. Lantz II, L. Tutorial: Soft Errors Induced by Alpha Particles / L. Lantz II, // IEEE Transactions on Reliability, June 1996- Vol. 45—Issue 2.-pp. 174-179.

72. May, Т. С. Alpha-particle-induced soft-errors in dynamic memories / Т. C. May, M. H. Wood // IEEE Trans. Electron Dev., 1979. Vol. ED-26. Issue 1. -pp. 2-9.

73. McKee, W. R. Cosmic Ray Neutron Induced Upsets as a Major Contributor to the Soft Error Rate of Current and Future Generation DRAMs / W. R. McKee, H. P. McAdams, E. B. Smith // 1996 IEEE Annual International Reliability Physics, 1996.-pp. 1-9.

74. Morelos-Zaragoza, R. H. The Art of Error Correcting Coding / R. H. Morelos-Zaragoza. First Edition, John Wiley & Sons, England, 2002-p.384.

75. Satoh, S. Geometric effect of multiple-bit soft errors induced by cosmic rayneutrons on DRAM / S. Satoh, Y. Tosaka, S. Wender // Electron Device Letters, IEEE, Jun 2000. -Vol. 21. Issue 6. pp. 310-312.

76. Shelton, C.P. Coding for Error Detection and Correction / C.P. Shelton. Carnegie Mellon University, Dependable Embedded Systems. USA, Pittsburgh, PA, 1999.-pp. 1-8.

77. Tosaka, Y. Cosmic Ray Neutron-Induced Soft Errors in Sub-Half Micron CMOS Circuits / Y. Tosaka, S. Satoh, // IEEE Electron Device Letters, March, 1997.-Vol. 18.-Issue 3.-p.99-101.

78. Ziegler, J. F. Terrestrial Cosmic Rays / J. F. Ziegler // IBM Journal of Research and Development, January 1996 —Vol. 40— Issue 1 — pp. 19-39.

79. Ziegler, J. F. IBM Experiments in Soft Fails in Computer Electronics (19781994) / J. F. Ziegler, H. W. Curtis, H. P. Muhlfeld // IBM Journal of Research and Development, January 1996 — Vol. 40 Issue 1. - pp. 3-18.

80. Ziegler, J. F. Effect of Cosmic Rays on Computer Memories / J. F. Ziegler, W. A. Lanford // Science, November 1979,- Vol. 206.- p. 776-788.

81. Ziegler, J. F. Cosmic Ray Soft Error Rates of 16-Mb DRAM Memory Chips / J. F. Ziegler, M. E. Nelson, J. D. Shell // IEEE Journal of Solid-State Circuits, February 1998.-Vol. 33.-Issue 2,-pp. 246-252.