Дефекты информации, хранимой на магнитном носителе можно подразделить на две основные группы:
1. Временные (обратимые) - это пыль, частицы отслоившегося лакового покрытия.
2. Постоянные (необратимые) - это различные царапины, трещины в покрытии, прилипшая грязь и т. п.
Для обнаружения и коррекции ошибок были разработаны системы кодирования информации с избыточностью (внедрение контрольных разрядов, образуемых с помощью выполнения определенных арифметических операций над всеми информационными разрядами).
Но следует учитывать при разработке и применении конкретной системы кодирования, что возможность обнаружения и коррекции ошибок возрастает с избыточностью кода, но одновременно усложняется алгоритм кодирования и декодирования и, как следствие, возрастает объем буферной памяти, и снижается скорость передачи информации, усложняется аппаратура кодирования и декодирования и, следовательно, система становится менее надежной.
Для двоичного кода М сообщений, каждое из которых имеет дину n, можно закодировать, если выполняется условие: 2n >=M или n>=log2 M.
Приведем примеры различных методов кодирования:
Пусть имеются четыре события:
А1, А2, А3, А4, причем вероятности их появления различны:
Р(А1)=0,5; Р(А2)=0,25; Р(А3)= Р(А1)=0,125.
Равномерное кодирование - без учета вероятности появления того или иного события.
Метод Фанно - А1=0 2; А2=10 2; А3=110 2; А4=111 2. Это пример неравномерного кодирования с учетом вероятности появления события. Система Фанно однозначно декодируема, поскольку ни одно А не является префиксом следующего. Такие системы кодирования называют префиксными.
Основные характеристики кодов:
| 1. Длина кода | n | Число символов, составляющих кодовое слово |
| 2. Основание кода | m | Количество отличных друг от друга значений импульсных признаков, используемых в кодовом слове |
| 3. Мощность кода | Мр | число разрешенных кодовых слов |
| Полное число кодовых слов | М | все возможные кодовые слова |
| 4. Число информационных символов | k | без комментариев |
| 5. Число проверочных символов | r | без комментариев |
| 6. Избыточность кода | R | R=r/n |
| 7. Скорость передачи кодовых слов | R’ | R’=k/n |
| 8. Кодовое расстояние | d | Число несовпадающих позиций двух кодовых слов |
Имея один избыточных символ, можно обнаружить только нечетное количество ошибок. Поэтому используют другой метод. Объясним на примере:
Пусть должно прийти 9-разрядное число. Расположим приходящие разряды следующим образом:
| В1 | В2 | В3 | С1 | Пусть | В1Å В4Å В7 = С4 | |
| В4 | В5 | В6 | С2 | В4Å В5Å В6 = С2 | В2Å В5Å В8 = С5 | |
| В7 | В8 | В9 | С3 | В7Å В8Å В9 = С3 | В3Å В6Å В9 = С6 | |
 С4
| С5 | С6 | С7 | С1 Å С2 Å С3 Å С4 Å С5 Å С6= С7 |
Пусть приходит число 011010001. Пусть произошла ошибка в 7-ом разряде
| Передано | Принято | |||||||||
При сравнении В7Å В8Å В9 = С3 в строке
В1Å В4Å В7 = С4 в столбце
Следовательно, ошибочный разряд локализован можно исправить.
Но это был случай единичной ошибки, а с двойной ошибкой этот метод не справляется, то есть определить может, но исправить - нет.
На рисунке видно, что, используя этот метод, нельзя понять, где произошла ошибка (В2, В3, В8, В9).
Для дальнейшего объяснения d(x,y) между двумя кодовыми словами х и у называется число несовпадающих позиций. Пример: х=01101, у=00111 d(x,y)=2. Это расстояние называется кодовым расстояние Хемминга.
Итак, код способен исправить любые комбинации из q или меньшего числа ошибок тогда и только тогда, когда его кодовое расстояние > 2q. В настоящее время только для кодов с dmin получено такое соотношение между числом проверочных символов r и длиной кода n:
r>= log2 (n+1).
Циклические коды
Циклическими кодами называются такие коды, которые с любым своим вектором содержит также его циклический сдвиг. Циклические коды основаны на представлении передаваемых данных в виде полинома (многочлена) и используются при последовательной передаче информации между Процессором и ВЗУ.
а(х)= а0+а1 х+а2 х2+...+ аn-1 хn-1 Для вектора а(а0, а1,..., аn-1).
Циклический сдвиг а’(х)= аn-1 +а0x +а1 х2+...+ аn-2 хn-1 .
С помощью этих кодов можно обнаруживать:
· Ошибки в 1 бите, если порождающий многочлен содержит > 1 члена,
· Ошибки в 2 битах, если порождающий многочлен содержит 3 члена,
· Ошибки в нечетном количестве битов, если порождающий многочлен содержит множитель (х+1),
· Пакеты ошибок длиной менее к+1 бит, если порождающий многочлен содержит множитель (х+1), и один множитель с 3мя членами и более (к+1 - число бит порождающего многочлена).
Принцип построения циклических кодов
Каждая кодовая комбинация Q(x) умножается на одночлен xr , а затем делится на многочлен. Степень каждого одночлена, входящего в Q(x), повышается на r. При делении получается С(х) такой же степени, что и Q(x), и остаток Р(х) степени не более r-1, наибольшее число разрядов которого <=r.
Q(x) xr / g(x) = C(x)+ P(x)/g(x)..............................(1)
В ЭВМ используется метод умножения кодовой комбинации Q(x) на одночлен xr и прибавлением к этому произведению остатка Р(х) на порождающий многочлен g(x).
Реально умножается на фиксированный многочлен типа x3Å x2Å 1
Схема умножения на многочлен.
| Вначале все ячейки содержа 0. Пусть требуется умножить x4 Å x2 Å1 на x3 Å x2 Å1 | |
| 1 такт | На вход поступает единичный коэффициент при старшей степени x4, запоминается в 1-й ячейке памяти и передается на выход. |
| 2 такт | На вход поступает 0-й коэффициент при x3. Содержимое первой ячейки приходит во вторую, на выходе сумматора появляется 1, которая, суммируясь с выходом 3-й ячейки, появляется на выходе 2-го сумматора |
| 3 такт | На вход поступает коэффициент при x2. Он запоминается в 1-й ячейке памяти и передается на выход. |
| 4 такт | На вход поступает 0-й коэффициент при x1. Первый сумматор имеет на выходе 1, а второй - 0. |
| 5 такт | На вход сумматора поступает 1 - коэффициент при x0. |
| 6-8 такты | Учитывая, что после умножения многочленов старший коэффициент имеет 7-ю степень, необходимо сдвинуть на 3 разряда (убираются разряды, содержащие 0) |
| Такт | Вх. символ | Содержимое регистра после очередного сдвига | Вых. символ |
| -- | -- | ||
Схема деления на многочлен
На вход со старших степеней коэффициенты, а на выход - коэффициенты частного. По окончании деления в регистре сдвига слева направо оказываются записанными коэффициенты остатка, начиная с младших степеней.
Пример - разделить x5 Å x4 Å x3 Å x2 Å1 на x3 Å x2 Å1.
| Такт | Вх. символ | Содержимое регистра после очередного сдвига | Вых. символ |
| -- | -- | ||
| -- |
Рассмотрим процесс обнаружения и исправления ошибок. Пусть n=7 и необходимо исправить q=1. Из формул n=2c-1 c кодовым расстоянием dmin>=2q+1 и r<=cq Þ c=3 и r=3. Так как 3 делится без остатка на 1 и 3, то сомножителями двучлена будут все неприводимые многочлены степени 1 и 3. Пусть имеется кодовое слово x3 Å x2 Å1.
Запись
Первые 4 такта Клапан 1 закрыт и информационные символы кодового слова поступают через комбинационную схему на выход и одновременно на схему, которая в соответствии с формулой 1 умножает кодовое слово на х3 и делит на g(x). В регистре получается остаток от деления. Далее клапан 1 открывается, производит 3 сдвига и остаток в виде контрольных символов выводится из регистра. В результате формируется кодовое слово с контрольными символами
х6+х4+х3+х2 -> 1011100
Чтение
После приема всей информации проверяется содержимое всех разрядов регистра, и если все нули, то ошибок нет.