Введение 4
1 Аналитический обзор методов и алгоритмов представления и обработки
данных в системе остаточных классов 6
1.1 Система остаточных классов и её свойства 6
1.2 Анализ методов перевода чисел из ПСС в СОК 11
1.2.1 Преобразователи ПСС в СОК с использованием ПЗУ 12
1.2.2 Преобразование двоичного кода в СОК с использованием свойств
периода 13
1.2.3 Прямое преобразование с использованием метода Паскаля 16
1.2.4 Прямое преобразование для FPGA 18
1.2.5 Модули специального вида (2п ± к) 20
1.3 Анализ методов перевода чисел из СОК в ПСС 21
1.3.1 Китайская теорема об остатках 22
1.3.2 Приближенный метод 27
1.3.3 Обобщённо позиционная система счисления (ОПСС) 34
1.3.4 КТО-I, КТО-II, КТО-III 38
1.3.5 Функции ядра 41
1.4 Масштабирование оснований СОК 44
1.5 Выводы по первой главе 49
2 Коды исправления ошибок в модулярном коде 51
2.1 Метод проекции 52
2.2 Метод синдрома 56
2.2.1 Выделение синдромов для идентификации ошибок 56
2.2.2 Обнаружение и исправления ошибок 62
2.2.3 Пример 67
2.2.4 Доказательство корректности метода исправления ошибок на базе
синдрома 69
2.3 Выводы по второй главе 76
3 Модификация методов обнаружения локализации и исправления ошибок .... 77
3.1 Модификация метода синдрома в СОК 77
3.2 Выбор оснований СОК 79
3.3 Выводы по третьей главе 82
Заключение 84
Список использованных источников 85
Требования к повышению производительности, снижению энергопотребления портативной электроники позволили уменьшить размеры оборудования, но в то же время возникли проблемы надёжности устройств. Обеспечение надёжности хранения и обработки информации, снижения энергопотребления являются актуальными проблемами цифровой экономики. Обеспечение отказоустойчивости цифровых систем представляется наилучшим решением для повышения надёжности. Отказоустойчивость систем может быть обеспечена как аппаратной избыточностью, например, использованием RAID- массивов, так и программной избыточностью - с использованием кодов исправления ошибок, логики самоконтроля, репликации модулей, реконфигурации, однако данные методы имеют следующие недостатки: высокая избыточность, необходимость интенсивных вычислений.
Одним из методов обеспечения надёжности является использование системы остаточный классов (СОК). СОК является непозиционной системой счисления, в которой число может быть представлено в виде вектора чисел меньшей размерности, представляющих собой остатки от деления на набор взаимно простых чисел, называемых модулями. Путём добавления избыточных модулей в существующий набор модулей СОК получающаяся избыточная СОК (ИСОК) может использоваться, чтобы обнаружить и исправить ошибки, не изменяя допустимый диапазон исходной информации. Методы обнаружения и исправления ошибок, основанные на ИСОК, способны исправлять ошибки арифметической обработки [1] из-за шума, производственных дефектов, изменений в процессе, напряжении и температуре или даже преднамеренного ввода неисправности в дополнение к ошибкам передачи или хранения. Вследствие независимости разрядов числа, представленного в СОК, любая ошибка, вносимая в канал модуля, не будет распространяться на другие каналы модуля [2]. Другими словами, ошибочные биты в разряде остатка имеют локализованный эффект. Эта уникальная вычислительная возможность 4
исправления ошибок особенно полезна в приложениях надёжного хранения, безопасности, биомедицины, которые не допускают ошибок.
Объект исследования: Система остаточных классов.
Предмет исследования: Методы и алгоритмы обнаружения, локализации и исправления ошибок.
Цели исследования:
1. Обзор методов и алгоритмов представления и обработки данных в системе остаточных классов, исследование кодов исправления ошибок в модулярном коде.
2. Модификация методов обнаружения, локализации и исправления ошибок.
Основные задачи выпускной квалификационной работы:
1. Исследовать теоретические основы представления и обработки данных в системе остаточных классов.
2. Предложить эффективные алгоритмы обнаружения и исправления ошибок для аппаратной реализации.
3. Проанализировать модификации методов обнаружения, локализации и исправления ошибок.
Система остаточных классов (СОК) за счёт непозиционного представления чисел в ряде случаев является достаточно эффективной заменой позиционным системам счисления, что достигается за счёт эффективного использования параллелизма и снижения разрядности операндов
В выпускной квалификационной работе были предложены эффективные для аппаратной реализации методы для обнаружения и исправления ошибок в модулярном коде, модифицирован метод синдрома для системы остаточных классов.
Для достижения этой цели в выпускной квалификационной работе решены задачи:
1. исследованы теоретические основы представления и обработки данных в системе остаточных классов, рассмотрены достоинства и недостатки данной системы.
2. предложены эффективные алгоритмы обнаружения и исправления ошибок для аппаратной реализации.
3. проанализированы модификации методов обнаружения локализации и исправления ошибок.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
