о кодах корректировок ошибок
Jan. 16th, 2008 04:30 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
В зиван написал, потом решил, что есть смысл такую Мудрость и для общего употребления выложить:
В простейшем случае коды корректировки ошибок можно представлять себе так:
У нас есть N^2 бит данных. Мы их представляем в виде квадратика N x N:
1 0 1
0 0 1
1 0 0
Теперь по каждой вертикали и горизонтали считаем четность:
1 0 1 | 0
0 0 1 | 1
1 0 0 | 1
-------
0 0 0
Эта четность добавляет нам N*2 контрольных бит. Теперь если какой-то один бит меняется, то четность в его строке и столбце перестает совпадать. Таким образом, зная строку и столбец, мы знаем, какой бит испортился, и можем поменять его взад.
Аналогично вместо 2-мерного квадрата можно взять 3-мерный куб. Тогда на N^3 бит данных мы получаем 3*N контрольных бит. Ну, или дальше n-мерный куб.
У Хэмминга, если я правильно помню, все устроено в-принципе подобно, но более хитро. Смысл такой: каждому числу из N бит дается не одно представление, а K+1, где K - количество бит, включая контрольные. Из них одно - "стандартное", а остальные K отличаются от него значением одного бита (т.е. кодовое расстояние от стандарта получается равным 1).
Потом, когда мы читаем числа взад, то проверяем значения на "стандартность". Если обнаружено нестандартное представление, то оно заменяется на стандартное, и таким образом происходит коррекция ошибок. После этого стандартное представление отображается на изначальное число.
Соответственно, для такого кодирования требуется K=ceiling( log2((2^N)*(K+1)) ) бит. Ну, а при K=2^n-1 второй множитель (K+1) получается степенью двойки, результат log2 получается сразу целым числом, и в коде не остается неиспользуемых значений.
То есть, для K=3 получаем 2^3 = (2^N)*(3+1), N = 1, для K=7 получаем 2^7 = (2^N)*(7+1)), N=4.
Ну, а как именно строится таблица преобразования - я не помню :-)
P.S. в изначальном варианте я перепутал количество представлений
В простейшем случае коды корректировки ошибок можно представлять себе так:
У нас есть N^2 бит данных. Мы их представляем в виде квадратика N x N:
1 0 1
0 0 1
1 0 0
Теперь по каждой вертикали и горизонтали считаем четность:
1 0 1 | 0
0 0 1 | 1
1 0 0 | 1
-------
0 0 0
Эта четность добавляет нам N*2 контрольных бит. Теперь если какой-то один бит меняется, то четность в его строке и столбце перестает совпадать. Таким образом, зная строку и столбец, мы знаем, какой бит испортился, и можем поменять его взад.
Аналогично вместо 2-мерного квадрата можно взять 3-мерный куб. Тогда на N^3 бит данных мы получаем 3*N контрольных бит. Ну, или дальше n-мерный куб.
У Хэмминга, если я правильно помню, все устроено в-принципе подобно, но более хитро. Смысл такой: каждому числу из N бит дается не одно представление, а K+1, где K - количество бит, включая контрольные. Из них одно - "стандартное", а остальные K отличаются от него значением одного бита (т.е. кодовое расстояние от стандарта получается равным 1).
Потом, когда мы читаем числа взад, то проверяем значения на "стандартность". Если обнаружено нестандартное представление, то оно заменяется на стандартное, и таким образом происходит коррекция ошибок. После этого стандартное представление отображается на изначальное число.
Соответственно, для такого кодирования требуется K=ceiling( log2((2^N)*(K+1)) ) бит. Ну, а при K=2^n-1 второй множитель (K+1) получается степенью двойки, результат log2 получается сразу целым числом, и в коде не остается неиспользуемых значений.
То есть, для K=3 получаем 2^3 = (2^N)*(3+1), N = 1, для K=7 получаем 2^7 = (2^N)*(7+1)), N=4.
Ну, а как именно строится таблица преобразования - я не помню :-)
P.S. в изначальном варианте я перепутал количество представлений