33. Корректирующие коды. Классификация. Принципы формирования кода Хемминга (на примере) и техническая реализация аппаратуры для исправления одиночных ошибок.
Все корректирующие коды можно разделить по обнаруживающей способности:
- с коррекцией одиночной и обнаружением двойной ошибки (КО-ОД) (например, код Хемминга);
- коды с дополнит. способностью обнаружения кратной ошибки в одной группе битов (КО-ОД-ООГ);
- коды с коррекцией ошибок в одной группе и обнаружением в двух группах (КОГ-ОГД);
- коды с коррекцией двойных и обнаружением тройных ошибок (КД-ОТ) [5].
Код Хэмминга формир. перед записью информации и добавл. к информационным разрядам слова.
Формирование КХ: разрядность 2r n + 1 или 2r - r - 1 k,
где k - число разрядов информационного слова;
r - число дополнительных контрольных разрядов; n = r + k - передаваемое кодовое число.
Для формирования КХ используется матрица Н размерности rxn, которая удовл. Усл.:
1) векторы-столбцы матрицы Н не должны быть нулевыми и должны отличаться друг от друга;
2) сумма двух векторов-столбцов не должна равняться нулю или любому третьему вектору-столбцу.
34. Аппаратура и алгоритм исправления одиночных ошибок на основе кода ко-од на примере.
Рассмотрим алгоритм работы системы контроля КО-ОД.
При записи:
- информация из ПР поступает в RgDI (64 бита) и 8 бит нечетности для каждого байта слова, а адрес для записи - в RgA;
- с выхода RgDI через MS1 слово поступает на генератор кода Хэмминга GKH для формирования кода Хэмминга СТ-С0 и контрольных бит нечетности байт К7-К0. На схеме сравнения (Сх.ср.) определяется правильность приема информации из процессора в RgDI путем сравнения бит КК из ПР и бит нечетности, сформированных схемой GKH;
- если сигнал ошибки передачи по нечетности не выработан, то сформированный код Хэмминга СТ-С0 с выходов GKH вместе с информационными разрядами слова записывается в ОП;
- если выработан сигнал ошибки передачи по нечетности, то выполняется попытка повторной передачи информации из процессора с контрольными битами КК для классификации типа отказа: постоянный или случайный (сбой) (иногда до 8 раз);
- если отказ постоянный, то устанавливается триггер ошибки и вырабатывается сигнал прерывания от схем контроля, иначе запись слова и КХ СТ-С0 в ОП.
Ч
тение
из ОП
- Из ОП считываются 64 бита слова и 8 бит КХ СТ-С0. Считанное слово через MS1 поступает на схемы генератора кода Хэмминга.
- Полученные в GKH биты СТ-С0н сравниваются со считанными из ОП битами СТ-С0сч. и при их несовпадении схема определения синдрома ошибки (Сх.ОСО) формирует код синдрома ошибок ST-S0, определяющего номер ошибочного бита в слове, а также тип ошибки на схеме классификации ошибок (одиночная или двойная).
Адрес слова ОП, его синдром ошибки и тип ошибки запоминаются в специальном регистре ошибок для последующей записи его значения в журнал ошибок ОС.
При одиночной ошибке схема определения вектора ошибки (Сх.ОВО) формирует код вектора ошибки Е, а в схеме коррекции ошибок выполняется ее исправление путем инверсии ошибочного бита, а также выполняется изменение бита нечетности того байта, в котором выполнена коррекция. Скорректированная информация поступает в RgRD, а из него в процессор. Неисправимая (двойная) ошибка ОП вызывает установку бита ошибки в Тош и прерывание от схем контроля. Все случаи ошибок, обнаруженные при обращении к памяти, фиксируются в журнале ошибок ОС.
35. Методы, алгоритмы и техническая реализация методов исправления двойных ошибок на основе корректирующих кодов (алгоритмические, аппаратные, последовательная коррекция для исправления одиночных и двойных ошибок в памяти и др.)
Последовательная коррекция
Метод основан на применении кода КО-ОД и позволяет исправлять большинство двойных неисправимых ошибок. Алгоритм работы схемы имеет основан на запоминании синдромов жестких исправимых одиночных ошибок в специальной памяти, построенной на основе ассоциативного запоминающего устройства (АЗУ).
При записи:
- информация из ПР поступает в RgDI (64 бита и 8 бит нечетности для каждого байта), а адрес для записи - в RgA;
- с выхода RgDI через MS1 слово поступает на ГКХ и бит нечетности GKH для формирования КХ СТ-С0 и контрольных бит нечетности байт К7-К0. На схеме сравнения (Сх.ср.) определяется правильность приема информации из процессора в RgDI путем сравнения бит КК нечетности, принятых из ПР, и бит нечетности, сформированных схемой GKH;
- если сигнал ошибки передачи по нечетности не выработан, то сформированный код Хэмминга СТ-С0 с выходов GKH вместе с информационными разрядами слова записывается в ОП;
- если выработан сигнал ошибки передачи по нечетности, то выполняется попытка повторной записи для классификации типа отказа: постоянный или случайный (сбой) (иногда до 8 раз);
- если отказ постоянный, то устанавливается триггер ошибки и вырабатывается сигнал прерывания от схем контроля, иначе запись слова и КХ СТ-С0 в ОП.
При чтении:
- При считывании из ОП одновременно осуществляется обращение к АЗУ для поиска по всем адресам с чтением синдрома первой одиночной ошибки при формировании признака АTeg.
- Если, А/Teg то при одиночной ошибке ее синдром ST-S0 и адрес (Теg) записываются в АЗУ, а одиночная ошибка и КК нечетности исправляются средствами кода КО-ОД.
- Если при считывании выработан сигнал двойной ошибки и ATeg, то вырабатывается сигнал прерывания от схем контроля о неисправимой ошибке.
- Если ATeg и выработан сигнал одиночной ошибки, то она исправляется схемой коррекции кода КО-ОД, а ее синдром, если он не равен нулю, вновь записывается в АЗУ на место старого синдрома, так как при первой записи синдрома ошибка могла быть вызвана случайным самоустранимым сбоем и в дальнейшем произойдет неправильное исправление ошибки. Если новый синдром равен нулю, то в ячейке АЗУ соответствующий бит достоверности данных сбрасывается. Также выполняется коррекция КК нечетности одного из байт слова.
- Если ATeg и выработан сигнал двойной ошибки, то начинает работу схема последовательной коррекции: первая ошибка корректируется по информации из АЗУ памяти синдромов ST'-S0' и исправленное слово вновь записывается в RgDO для формирования нового кода СТ-С0н и синдрома ошибки ST-S0, а оставшаяся одиночная ошибка и КК исправляются схемой коррекции кода КО-ОД.
Схема управления коррекцией известной жесткой ошибки, хранимой в АЗУ, запускается схемой классификации типа ошибки.
Перезапись в инверсном коде.
Алгоритм состоит из следующих шагов:
1. Чтение слова W1 из ОЗУ.
2. Если в слове W1 обнаружена одиночная ошибка, то она исправляется схемами коррекции КО-ОД и слово передается по назначению.
3. Если в слове W1 обнаружена неисправимая ошибка, то в эту же ячейку ОЗУ записывается инверсия считанного слова W2 = ~W1 считанное. Затем слово снова считывается и инвертируется W3 = ~W2 считанное;
4. Если в слове W3 схемами контроля обнаружена одиночная ошибка, то она исправляется схемами коррекции КО-ОД, а исправленное слово передается по назначению.
5. Если ошибок нет, то слово W3 считается безошибочным и передается по назначению.
6. Если в слове W3 обнаруживается неисправимая ошибка, то считается, что она алгоритмически неисправима и вырабатывается прерывание от схем контроля.
