|
Читайте также: |
Рассмотрим рис. 4.9, на котором помимо контроля четности по строкам для всей приведенной информации рис. 4.8 введен еще контроль четности по столбцам (нижняя 8-я строка)
Рис. 4.9. Побайтовое обнаружение и исправление одиночной ошибки в блочном кодере
При наличии одиночной ошибки в этой 8x8 = 64-битовой матрице можно указать не только строку, содержащую ошибку, но и столбец с ошибкой, а значит — ошибочный бит, лежащий на пересечении строки и столбца (например, если обнаружена ошибка в 4 строке (1 в 8 столбце), 8-байтовой последовательности, а также в 4-ом столбце (1 в 8 строке), то, таким образом, обнаружен ошибочный бит в 4 строке 4-го столбца матрицы).
Итак, если обнаружен ошибочный бит, то он может быть элементарно исправлен: если в данном примере — 4 строка — 4 столбца — ошибка — 0, то вместо него ставится 1 (или наоборот).
Таким образом, матрица рис. 4.9 позволяет, при ее реализации в виде систематических байтовых кодеров [рис. 4.9 — (п, к) = (64, 49)] обнаружить и исправить одиночные ошибки. Однако, кратные ошибки этой схемой исправить невозможно. Для коррекции кратных ошибок применяются более совершенные и сложные схемы
След слайд
Рассмотрим, как можно использовать дополнение до четности для исправления ошибки на примере кодирования массива из 9 бит: 100 110 101.
Запишем этот массив в виде матрицы три на три и дополним каждую строку и столбец матрицы до четного количества единиц.
Таким образом, исходный массив после кодирования примет вид: 100 110 101 100 111. Допустим, что после передачи данных произошла ошибка в 4-ом бите сообщения, и полученный массив принял вид: 100 010 101 100 111.
Произведем его декодирование, для чего запишем в виде матрицы 4 на 4, где матрица 3 на 3 - исходные данные, которые надо было передать, остальные элементы матрицы – коды дополнения до четности. Проведя суммирование бит в строках и столбцах, видим, что в первом столбце и второй строке количество единиц - нечетное, а, следовательно, в них содержатся ошибки.
Так как дополнение до четности позволяет обнаружить только одну ошибку, то примем за аксиому, что в блоке только одна ошибка. Теперь становится очевидным, что ошибочный бит может быть только на пересечении строки и столбца с нечетным количеством единиц. Инвертировав его на противоположный, мы восстановим испорченные данные.
Данный метод позволяет исправлять только однократные ошибки, поэтому использовать его для передачи большого массива информации нецелесообразно. Однако, его можно легко усовершенствовать, разбив исходный массив на блоки данных с N слоями, M строками и К столбцами и проведя дополнение до четности всех строк, столбцов и элементов с одинаковыми индексами строк и столбцов. Для простоты изложения столбцы назовем столбцами Y, а элементы с одинаковыми индексами строк и столбцов назовем столбцами Z.
След слайд
Рассмотрим этот алгоритм на примере кодирования следующего массива данных: 101 110 000 101 100 011 001 010 111.
1) Формируем 3 массива из 9 элементов. В первый массив записываем первые девять бит исходных данных, во второй массив - элементы с 10 по 18, в третий массив – оставшиеся данные.
След слайд
2) Дополняем все строки, столбцы Y и Z до четности. (В таблицах биты дополнения до четности выделены жирным шрифтом).
3) Закодированная исходная последовательность приняла вид: 101 110 000 101 100 011 001 010 111 000 011 010 010 111 100 001 000 100
4) Предположим, что при передаче данных ошибки произошли во втором, шестом и двенадцатом битах информации, и полученные данные имеют вид: 111 111 000 100 100 011 001 010 111 000 011 010 010 111 100 001 000 100
След слайд
5) Проведем декодирование принятого блока и проверим на четность все строки, столбцы Y и Z.
Биты с возможными ошибками будут расположены на пересечении строк, столбцов Y и Z. В нашем случае - это будут биты c координатами: [1 (номер строки), 2 (номер столбца Y), 1 (номер слоя)], [1,3,1], [2,3,1], [1,3,2].
Среди этих бит могут быть, как биты с ошибками, так и верные биты, которые необходимо исключить.
В каждом наборе из трех бит (строке, столбце Y или столбце Z), проверяемом на четность, может быть зафиксирована только одна ошибка (две ошибки не приведут к изменению четности на нечетность). Основываясь на этом свойстве, исключаем из бит с возможными ошибками биты, лежащие на одной строке или столбце Y, или столбце H.
На одной строке лежат биты: [1,2,1], [1,3,1].
На одном столбце Y лежат биты: [2,3,1], [1,3,1].
На одном столбце Z лежат биты: [1,3,2], [1,3,1].
Таким образом, если убрать бит [1,3,1], исключается ситуация, когда на одной строке, столбце Y или Z лежат биты с возможными ошибками. Следовательно, бит [1,3,1] – верен, а остальные биты с возможными ошибками действительно их содержат. Инвертируя неверные биты, мы исправляем ошибки и получаем корректный исходный массив.
Повысить эффективность работы кодирования можно, например, заменив дополнение до четности на контрольное суммирование, позволяющее фиксировать большее количество ошибок.
Блочное кодирование обладает высокой надежностью, простотой реализацией, и получило широкое распространение. Существует большое разнообразие блочных кодов, обладающих различными возможностями по обнаружению и исправлению ошибок, среди которых наиболее известны коды Хемминга.
След слайд
Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен.
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Также стоит отметить, что существуют более совершенные модификации данного алгоритма, которые позволяют обнаруживать (и если возможно исправлять) большее количество ошибок.
Сразу стоит сказать, что Код Хэмминга состоит из двух частей. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты (вычисленные особым образом). Вторая часть получает входящее сообщение и заново вычисляет контрольные биты (по тому же алгоритму, что и первая часть). Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. В противном случае, выводится сообщение об ошибке и при возможности ошибка исправляется.
Дата добавления: 2015-12-01; просмотров: 60 | Нарушение авторских прав