Код хемминга онлайн калькулятор
Битовый калькулятор онлайн (Silverlight)
※ Download: Код хемминга онлайн калькулятор
Допустим, мы хотим умножить полиномы 69 и 96. Онлайн программа решения задач курса предварительной алгебры геометрии. Цифры перед буквами — это код государства. Остаются незамеченными также ошибки, возникающие одновременно в двух, в четырёх или вообще в четном количестве разрядов.
Сдвигая створку, повернув ключ в один или половину оборота винта, нужно каждый раз закрывать и открывать оконную раму, проверяя ее работу. Кроме того, можно менять разрядность операндов: байт Byte , слово Short , двойное слово Integer, используется по умолчанию , учетверённое слово Long. При делении с остатком исходного многочлена на порождающий полином G x степени N можно получить 2 N различных остатков от деления.
Код Хэмминга — Эти k разрядов мы и будем считать контрольными. Неизвестные члены и есть позиции искаженных символов в кодовом слове v.
Систематический код, предложенный в 1949 г. Построение кода состоит в разбиении хемминга слова на взаимно пересекающиеся подмножества, причём каждому подмножеству ставится в соответствие один контрольный разряд проверки на чётность. Формирование подмножеств производится на основе анализа номера разряда при записи его в двоичной системе счисления. Все разряды кодового слова, имеющие единицу в первом младшем разряде калькулятор номера, включаются в первое подмножество, во втором — во второе и т. Затем подсчитывается количество единиц в разрядах, относящихся к каждому подмножеству, и в соответствующий контрольный разряд записывается единица, если это количество нечётно, и ноль — если чётно. Число разрядов в синдроме ошибки Код числу контрольных разрядов кода Хэмминга для данного слова.
imgur.com
Imgur: The magic of the Internet
Category Entertainment News Journey News & Media
Код Хэмминга.
Пример работы алгоритма / ХабрПрежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:
Коды Хэмминга — наиболее известные и, вероятно, первые из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.
Другими словами, это алгоритм, который позволяет закодировать какое-либо информационное сообщение определённым образом и после передачи (например по сети) определить появилась ли какая-то ошибка в этом сообщении (к примеру из-за помех) и, при возможности, восстановить это сообщение. Сегодня, я опишу самый простой алгоритм Хемминга, который может исправлять лишь одну ошибку.
Также стоит отметить, что существуют более совершенные модификации данного алгоритма, которые позволяют обнаруживать (и если возможно исправлять) большее количество ошибок.
Сразу стоит сказать, что Код Хэмминга состоит из двух частей. Первая часть кодирует исходное сообщение, вставляя в него в определённых местах контрольные биты (вычисленные особым образом). Вторая часть получает входящее сообщение и заново вычисляет контрольные биты (по тому же алгоритму, что и первая часть). Если все вновь вычисленные контрольные биты совпадают с полученными, то сообщение получено без ошибок. В противном случае, выводится сообщение об ошибке и при возможности ошибка исправляется.
Для того, чтобы понять работу данного алгоритма, рассмотрим пример.
Подготовка
Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.
На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать.
Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:
и
После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):
Было:
Стало:
Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».
Вычисление контрольных бит.
Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит (как неожиданно), но не от всех, а только от тех, которые этот контрольных бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Не очень понятно, но по картинке, думаю, станет яснее:
Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.
Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу.
Вот и всё! Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем применять первый вариант).
и для второй части:
Вот и всё! Первая часть алгоритма завершена.
Декодирование и исправление ошибок.
Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):
Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:
Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили.
Заключение.
В данном примере, я взял длину информационного сообщения именно 16 бит, так как мне кажется, что она наиболее оптимальная для рассмотрения примера (не слишком длинная и не слишком короткая), но конечно же длину можно взять любую. Только стоит учитывать, что в данной простой версии алгоритма на одно информационное слово можно исправить только одну ошибку.
Примечание.
На написание этого топика меня подвигло то, что в поиске я не нашёл на Хабре статей на эту тему (чему я был крайне удивлён). Поэтому я решил отчасти исправить эту ситуацию и максимально подробно показать как этот алгоритм работает.
Источники.
1. Википедия
2. Calculating the Hamming Code
Программа проверки кода Хэмминга
Программа проверки кода ХэммингаЭтот инструмент сгенерирует 10-битное случайное число (от 1 до 1024), а затем сгенерирует кодовое слово Хэмминга (путем добавления 4 битов четности). Любой один бит в кодовом слове (бит данных или бит четности) может быть изменен, и при проверке значений четности будет обнаружена одиночная битовая ошибка, которую можно будет исправить.
| Двоичный код для этого номера: | |
| Старший бит … Младший бит |
| LSB … MSB | ||||||||||||||||||||||||||||
| Значение в обратном двоичном формате: | г 1 | г 2 | д 3 | г 4 | д 5 | д 6 | д 7 | д 8 | д 9 | д 10 | ||||||||||||||||||
| Значения четности: | р 1 | р 2 | р 3 | р 4 | ||||||||||||||||||||||||
| б 1 | б 2 | б 3 | б 4 | б 5 | б 6 | б 7 | б 8 | б 9 | б 10 | б 11 | б 12 | б 13 | б 14 | |||||||||||||||
| Кодовое слово: | р 1 | р 2 | г 1 | р 3 | д 2 | д 3 | г 4 | р 4 | д 5 | д 6 | р 7 | д 8 | д 9 | д 10 | ||||||||||||||
Измените одно единственное значение в кодовом слове и щелкните, чтобы проверить и исправить одиночную ошибку бита: | ||
| p 1 = d 1 + d 3 + d 5 + d 7 + d 9 % 2 | = | |
| p 2 = d 2 + d 3 + d 6 + d 7 + d 10 1 2 % | = | |
| p 4 = d 4 + d 5 + d 6 + d 7 % 2 | = | |
| р 8 = д 8 + д 9 + д 10 % 2 | = | |
EE4253 Онлайн-инструмент для генерации кодовых слов
EE4253 Онлайн-инструмент для генерации кодовых слов| ECE4253 Цифровая связь | |
| Факультет электротехники и вычислительной техники — Университет Нью-Брансуика, Фредериктон, Нью-Брансуик, Канада | |
Этот онлайн-инструмент генерирует наборы кодовых слов с определенными свойствами. Учитывая полученное кодовое слово, это слово может быть отправлено для обнаружения или исправления ошибок по сравнению с сгенерированным набором действительных кодовых слов.
Здесь используется поиск методом грубой силы, чтобы продемонстрировать наборы кодовых слов, обладающие свойствами минимального расстояния. Для Для более структурированного подхода к генерации кодовых слов может подойти онлайн-генератор кодов BCH.
Выберите значения длины кодового слова (L) и минимального расстояния Хэмминга (D) между кодовыми словами. Нажмите «Создать», чтобы увидеть список кодовых слов с этими свойствами. Введите кодовое слово, имеющее L-биты, и нажмите «Получить», чтобы увидеть, как это кодовое слово будет получено.
L = 234567891011121314151617 Д = 234567891011121314151617
Сгенерированные 7-битные кодовые слова выделены ниже полужирным шрифтом. где каждый помечен для удобства.
Расстояние между каждым кодовым словом и другими кодовыми словами показано справа. Расстояние между любыми двумя
кодовых слов должно быть не менее 3 в каждом случае.
7-битные КОДОВЫЕ СЛОВА [D=3]
================================================== ==========
А Б В Г Д Е Ж З И К Л М Н О П
А 0000000 : 0 3 3 4 3 4 4 3 4 3 3 4 3 4 4 7 А
В 0000111 : 3 0 4 3 4 3 3 4 3 4 4 3 4 3 7 4 В
С 0011001 : 3 4 0 3 4 3 3 4 3 4 4 3 4 7 3 4 С
Д 0011110 : 4 3 3 0 3 4 4 3 4 3 3 4 7 4 4 3 Д
Е 0101010 : 3 4 4 3 0 3 3 4 3 4 4 7 4 3 3 4 Е
F 0101101 : 4 3 3 4 3 0 4 3 4 3 7 4 3 4 4 3 F
Г 0110011 : 4 3 3 4 3 4 0 3 4 7 3 4 3 4 4 3 Г
Н 0110100 : 3 4 4 3 4 3 3 0 7 4 4 3 4 3 3 4 Н
I 1001011 : 4 3 3 4 3 4 4 7 0 3 3 4 3 4 4 3 I
J 1001100 : 3 4 4 3 4 3 7 4 3 0 4 3 4 3 3 4 J
К 1010010 : 3 4 4 3 4 7 3 4 3 4 0 3 4 3 3 4 К
л 1010101 : 4 3 3 4 7 4 4 3 4 3 3 0 3 4 4 3 л
М 1100001 : 3 4 4 7 4 3 3 4 3 4 4 3 0 3 3 4 М
Н 1100110 : 4 3 7 4 3 4 4 3 4 3 3 4 3 0 4 3 Н
О 1111000 : 4 7 3 4 3 4 4 3 4 3 3 4 3 4 0 3 О
Р 1111111 : 7 4 4 3 4 3 3 4 3 4 4 3 4 3 3 0 Р
А Б В Г Д Е Ж З И К Л М Н О П
================================================== ==========
ВСЕГО 16 КОДОВЫХ СЛОВ
|
