Введение к работе
Актуальность тсиы. В настоящее время в вычислительной технике находит широкое применение теория кодирования информации. Использование корректирующих кодов значительно увеличивает среднее время безотказной работы, снижает расходы на техническое обслуживание, уменьшает простои вычислительной системы. В связи с этим представляет интерес разработка кодов и способов их декодирования, обладающих требуемыми свойствами и достаточно простых при практической реализации. Выбор оптимального кода при заданных условиях хранения и передачи информации позволяет учитывать характер помех в устройствах обработки и хранения информации, а также затраты на усложнение аппаратуры, обусловленные необходимостью применения в них кодов.
С теорией помехоустойчивого кодирования методологически связана задача построения покрывающих кодов, которая представляет интерес как частный случай дискретной экстремальной задачи о покрытии на конечных множествах. Решение этого вопроса может найти практическое применение при квантовании информации в процессе ее передачи.
Диссертационная работа посвящена вопросам построения двоичных линейных покрывающих кодов, разработке и применению методов помехоустойчивого кодирования для повышения надежности полупроводниковых запоминающих устройств и для компактного тестирования конструктивных блоков в суперЭВМ.
Цель работы заключается в:
решении дискретной экстремальной задачи построения двоичных линейных покрыЕащкх кодов с малыми радиусами покрытия и плотностью покрытия близкой к минимальной;
построении проверочных матриц и разработке алгоритма декодиро-
вания двоичных кодов Боуза-Чоудхури-Хоквингема (БЧХ) с минимальным расстоянием 6, исправляющих двойные независимые ошибки и одиночные байты ошибок длины 4;
- разработке и реализации каскадного метода компактного тестиро
вания конструктивных блоков суперЭВМ на основе кодов, локализую
щих ошибки.
Научная новизна работы состоит в следующем.
Разработана модификация блочной конструкции проверочных матриц двоичных линейных покрывающих кодов с произвольными радиусами покрытия, предложенной А.А.Давыдовым. На ее основе построены бесконечные семейства кодов с малыми радиусами покрытия R = 2,э и 4. Покрытия, задаваемые этими кодами, лучше, чем покрытия известных кодов.
Построены проверочные матрицы и разработан алгоритм декодирования двоичных кодов БЧХ с минимальным расстоянием 6, способных наряду с исправлением двойных независимых ошибок исправлять одиночные байты ошибок длины 4 веса 4 и 3 и обнарукивать часть четырехкратных ошибок. Предполагается, что ошибки указанных типов не происходят одновременно. Приведены оценки обнаруживающей способности алгоритма декодирования.
Для контроля и диагностики конструктивных блоков суперЭВМ разработан каскадный метод компактного тестирования на основе кодов, локализующих ошибки.
Практическая ценность. Концепция модифицированной блочной конструкции проверочных матриц двоичных линейных покрывающих кодов, на основе которой построены бесконечные семейства кодов с малыми радиусами покрытия R = 2,э и 4, применима для получения кодов с радиусами покрытия R > 5.
С помощью разработанного алгоритма декодирования и построенных проверочных Матриц двоичных кодов БЧХ с минимальным расстоянием б может быть осуществлена защита от ошибок, возникавдих при хранения информации в полупроводниковых запоминающих устройствах суперЭВМ и учитывающая их байтовый характер.
Предложенный метод контроля и диагностики конструктивных блоков суперЭВМ на основе каскадного компактного тестирования с
использованием кодов, локализующих ошибки, позволяет уменьшить объем памяти, необходимый для хранения эталонных тестовых последовательностей.
Апробация работы. Основные результаты работы докладывались на семинаре отдела базового программного обеспечения Института проблем кибернетики РАН (1986 - 1992гг.), Всесоюзном семинаре молодых ученых и специалистов "Информатика и вычислительная техника" (г.Звенигород, 1986г.), Ill Международном семинаре по теории информации "Сверточные коды; связь со многими пользователями" (г.Сочи, 1987г.), I Всесоюзной конференции "Проблемы создания суперЭВМ, суперсистем и эффективность их применения" (г.Минск, 1988г.), IX Всесоюзной конференции по теории кодирования и передачи информации (г.Одесса, 1988г.), Научной школе-семинаре "Проблемы кибернетики" (г.Киев, 1990г.), и Международной конференции АССТ-2 (г.Ленинград, 1990г.), III Международной конференции АССТ-Э (Болгария, 1992Г-).
Публикации. Представляемые к защите результаты опубликованы в работах [1 - 11J.
Объем и структура диссертации. Диссертация состоит из введения, трех глав, заключения, приложения. Ее общий объем 109 страниц, в том числе 6 рисунков, 3 таблицы и список литературы из 57 наименований.
