2009-11-04 19 views

ответ

0

Вы, вероятно, следует прочитать страницу википедии об этом:

http://en.wikipedia.org/wiki/Error_detection_and_correction

Это звучит, как вы определенно хотите Хэмминга код:

http://en.wikipedia.org/wiki/Hamming_code#General_algorithm

Используя эту схему, вы можете посмотреть некоторые примерные значения из связанной таблицы.

+0

Почему downvote? Это правильный ответ. –

2

У вас есть 2^d различные виды пакетов длиной d бит, которые вы хотите отправить. Добавление ваших r бит к ним приводит их к кодовым словам длины d + r, поэтому теперь у вас есть 2^d возможных кодовых слов, которые вы могли бы отправить. Приемник может получать 2^(d + r) разные принятые слова (кодовые слова с возможными ошибками). Затем возникает вопрос, как вы сопоставляете полученные 2^(d + r) слова с 2^d кодовыми словами?

Это относится к minimum distance кода. То есть для каждой пары кодовых слов найдите количество бит, где они отличаются, а затем возьмите наименьшее из этих значений.

Допустим, у вас было минимальное расстояние 3. Вы получили слово и заметили, что это не одно из кодовых слов. То есть, есть ошибка. Таким образом, из-за отсутствия лучшего алгоритма декодирования вы переворачиваете первый бит и видите, есть ли его кодовое слово. Если вы не откидываетесь назад и переворачиваете следующий. В конце концов вы получите кодовое слово. Поскольку все кодовые слова различаются в трех позициях, вы знаете, что это кодовое слово является «самым близким» к принятому слову, так как вам нужно будет перевернуть 2 бита в полученном слове, чтобы перейти к другому кодовому слову. Если вы не получили кодовое слово с переворачиванием всего по одному биту за раз, вы не можете понять, где ошибки, поскольку есть несколько кодовых слов, которые вы могли бы получить, перевернув два бита, но вы знаете, что есть как минимум два ошибки.

Это приводит к общему принципу, что при минимальном расстоянии md вы можете обнаружить ошибки md-1 и исправить ошибки пола ((md-1)/2). Вычисление минимального расстояния зависит от того, как вы генерируете кодовые слова, иначе называемые кодом. Существуют различные границы, которые вы можете использовать для определения верхнего предела md на основе d и (d + r).

Павел упомянул код Хэмминга, что является хорошим примером. Он достигает Hamming bound. Для кода (7,4) Хэмминга у вас есть 4-битные сообщения и 7-битные кодовые слова, и вы достигаете минимального расстояния 3. Очевидно *, вы никогда не получите минимальное расстояние больше, чем количество добавляемых бит так что это самое лучшее, что вы можете сделать. Не слишком привыкайте к этому. Код Хэмминга является одним из немногих примеров нетривиального perfect code, и большинство из них имеют минимальное расстояние, меньшее количества добавляемых бит.

* Это не совсем очевидно, но я уверен, что это верно для нетривиальных кодов для исправления ошибок. Добавление одного бита четности дает вам минимальное расстояние до двух, что позволяет обнаружить ошибку. Код, состоящий из {000,111}, получает минимальное расстояние 3, добавляя только 2 бита, но это тривиально.