Многофункциональный контроллер ВЗУ

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

Пусть должно прийти 9-разрядное число. Расположим приходящие разряды следующим образом:

Пусть приходит число 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

 Схема умножения на многочлен.

1 2 3 4 5 6