Многофункциональный контроллер ВЗУРефераты >> Программирование и компьютеры >> Многофункциональный контроллер ВЗУ
На рисунке видно, что, используя этот метод, нельзя понять, где произошла ошибка (В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) |
|
Такт |
Вх. символ |
Содержимое регистра после очередного сдвига |
Вых. символ |
|
0 |
-- |
000 |
-- |
|
1 |
1 |
100 |
1 |
|
2 |
0 |
010 |
1 |
|
3 |
1 |
101 |
1 |
|
4 |
0 |
010 |
0 |
|
5 |
1 |
101 |
1 |
|
6 |
0 |
010 |
0 |
|
7 |
0 |
001 |
0 |
|
8 |
0 |
000 |
1 |
Схема деления на многочлен
На вход со старших степеней коэффициенты, а на выход - коэффициенты частного. По окончании деления в регистре сдвига слева направо оказываются записанными коэффициенты остатка, начиная с младших степеней.
Пример - разделить x5 Å x4 Å x3 Å x2 Å1 на x3 Å x2 Å1.
|
Такт |
Вх. символ |
Содержимое регистра после очередного сдвига |
Вых. символ |
|
0 |
-- |
000 |
-- |
|
1 |
1 |
100 |
0 |
|
2 |
1 |
110 |
0 |
|
3 |
1 |
111 |
1 |
|
4 |
0 |
110 |
0 |
|
5 |
1 |
111 |
1 |
|
6 |
1 |
010 |
-- |
