Код Хэмминга

редактировать

Двоичные коды Хэмминга
Код Хэмминга (7,4) (с r = 3)
Назван в честь	Ричард У. Хэмминг
Классификация
Тип	Код линейного блока
Длина блока	2 - 1, где r ≥ 2
Длина сообщения	2 - r - 1
Коэффициент	1 - r / (2 - 1)
Расстояние	3
Размер алфавита	2
Обозначение	[2 - 1, 2 - r - 1, 3] 2 - код
Свойства
совершенный код
v t

В информатике и телекоммуникациях, коды Хэмминга являются семейством линейного исправления ошибок коды. Коды Хэмминга могут обнаруживать до двух битовых ошибок или исправлять однобитовые ошибки без обнаружения неисправленных ошибок. Напротив, простой код четности не может исправлять ошибки и может обнаруживать только нечетное количество битов с ошибкой. Коды Хэмминга - это совершенные коды, то есть они достигают наивысшей возможной скорости для кодов с их длиной блока и минимальным расстоянием, равным трем. Ричард В. Хэмминг изобрел коды Хэмминга в 1950 году как способ автоматического исправления ошибок, вносимых считывающими устройствами перфокарт. В своей оригинальной статье Хэмминг развил свою общую идею, но специально сосредоточился на коде Хэмминга (7,4), который добавляет три бита четности к четырем битам данных.

В математические термины, коды Хэмминга - это класс двоичных линейных кодов. Для каждого целого числа r ≥ 2 существует код с длиной блока n = 2 - 1 и длиной сообщения k = 2 - r - 1. Следовательно, скорость кодов Хэмминга равна R = k / n = 1 - r / (2 - 1), что является максимально возможным для кодов с минимальным расстоянием, равным трем (т. е. минимальное количество битовых изменений, необходимых для перехода от любого кодового слова к любому другому кодовому слову, равно трем) и длина блока 2-1. Матрица проверки на четность кода Хэмминга строится путем перечисления всех столбцов длины r, которые не равны нулю, что означает, что двойной код из код Хэмминга - это сокращенный код Адамара. Матрица проверки на четность имеет свойство, состоящее в том, что любые два столбца являются попарно линейно независимыми.

Из-за ограниченной избыточности, которую коды Хэмминга добавляют к данным, они могут обнаруживать и исправлять ошибки только при низком уровне ошибок. Это случай компьютерной памяти (ECC-память ), где битовые ошибки крайне редки, а коды Хэмминга широко используются. В этом контексте часто используется расширенный код Хэмминга, имеющий один дополнительный бит четности. Расширенные коды Хэмминга достигают расстояния Хэмминга, равного четырем, что позволяет декодеру различать, когда возникает не более одной однобитовой ошибки, и когда возникают любые двухбитовые ошибки. В этом смысле расширенные коды Хэмминга предназначены для исправления одиночной ошибки и обнаружения двойной ошибки, сокращенно SECDED .

Содержание

1 История
- 1.1 Коды, предшествующие Хэммингу
  - 1.1.1 Четность
  - 1.1.2 Код два из пяти
  - 1.1.3 Повторение
2 кода Хэмминга
- 2.1 Общий алгоритм
3 кода Хэмминга с дополнительной четностью (SECDED)
4 [7,4 ] Код Хэмминга
- 4.1 Построение G и H
- 4.2 Кодирование
- 4.3 [7,4] Код Хэмминга с дополнительным битом четности
5 См. Также
6 Примечания
7 Ссылки
8 Внешние ссылки

История

Ричард Хэмминг, изобретатель кодов Хэмминга, работал в Bell Labs в конце 1940-х годов над компьютером Bell Model V., электромеханическая релейная машина с временем цикла в секундах. Ввод подавался на перфоленту шириной семь восьмых дюйма, которая имела до шести отверстий в ряду. В будние дни при обнаружении ошибок в реле машина останавливалась и мигала, чтобы операторы могли исправить проблему. В нерабочее время и в выходные дни, когда не было операторов, машина просто переходила к следующему заданию.

Хэмминг работал по выходным и все больше разочаровывался в необходимости перезапускать свои программы с нуля из-за обнаруженных ошибок. В записанном на пленку интервью Хэмминг сказал: «И поэтому я сказал:« Черт побери, если машина может обнаружить ошибку, почему она не может определить местоположение ошибки и исправить ее? »». В течение следующих нескольких лет он работал над проблемой исправления ошибок, разрабатывая все более мощный набор алгоритмов. В 1950 году он опубликовал то, что теперь известно как код Хэмминга, который до сих пор используется в таких приложениях, как память ECC.

Коды, предшествующие Хэммингу

Ряд простых кодов обнаружения ошибок использовался и до Коды Хэмминга, но ни один из них не был столь же эффективен, как коды Хэмминга в том же объеме.

Четность

Четность добавляет один бит, который указывает, было ли количество единиц (битовых позиций со значением один) в предыдущих данных четным или нечетное. Если при передаче изменяется нечетное количество битов, сообщение изменит четность, и в этот момент может быть обнаружена ошибка; однако бит, который изменился, мог быть самим битом четности. Наиболее распространенное соглашение состоит в том, что значение четности, равное единице, указывает, что в данных есть нечетное количество единиц, а значение четности, равное нулю, указывает, что существует четное количество единиц. Если количество измененных битов четное, контрольный бит будет действительным и ошибка не будет обнаружена.

Более того, четность не указывает, какой бит содержит ошибку, даже если он может ее обнаружить. Данные должны быть полностью отброшены и повторно переданы с нуля. В шумной среде передачи успешная передача может занять много времени или может никогда не произойти. Однако, хотя качество проверки четности оставляет желать лучшего, поскольку он использует только один бит, этот метод дает наименьшие накладные расходы.

Код два из пяти

Код два из пяти - это схема кодирования, которая использует пять битов, состоящих ровно из трех нулей и двух единиц. Это дает десять возможных комбинаций, достаточных для представления цифр 0–9. Эта схема может обнаруживать все одиночные битовые ошибки, все битовые ошибки с нечетными номерами и некоторые битовые ошибки с четными номерами (например, переворачивание обоих 1-битов). Однако он по-прежнему не может исправить ни одну из этих ошибок.

Повторение

Другой используемый в то время код повторял каждый бит данных несколько раз, чтобы гарантировать, что он был отправлен правильно. Например, если бит данных, который должен быть отправлен, равен 1, код повторения n = 3 отправит 111. Если три полученных бита не идентичны, во время передачи произошла ошибка. Если канал достаточно чистый, большую часть времени в каждой тройке будет изменяться только один бит. Следовательно, 001, 010 и 100 соответствуют 0 биту, а 110, 101 и 011 соответствуют 1 биту, причем большее количество одинаковых цифр ('0' или '1') указывает, что бит данных должен быть. Код с этой способностью восстанавливать исходное сообщение при наличии ошибок известен как код исправления ошибок. Этот код с тройным повторением является кодом Хэмминга с m = 2, поскольку имеется два бита четности и 2 - 2 - 1 = 1 бит данных.

Однако такие коды не могут правильно исправить все ошибки. В нашем примере, если канал переворачивает два бита и получатель получает 001, система обнаружит ошибку, но сделает вывод, что исходный бит равен 0, что неверно. Если мы увеличим размер битовой строки до четырех, мы сможем обнаружить все двухбитовые ошибки, но не сможем исправить их (количество битов четности четное); при пяти битах мы можем как обнаруживать, так и исправлять все двухбитовые ошибки, но не все трехбитные ошибки.

Более того, увеличение размера строки битов четности неэффективно, так как в нашем исходном случае пропускная способность снижается в три раза, а эффективность резко падает, когда мы увеличиваем количество дублирований каждого бита для обнаружения и исправьте больше ошибок.

Коды Хэмминга

Если в сообщение включено больше исправляющих ошибок битов, и если эти биты могут быть расположены так, что разные неправильные биты дают разные результаты ошибок, то плохие биты могут быть идентифицированы. В семибитном сообщении существует семь возможных однобитовых ошибок, поэтому три бита контроля ошибок потенциально могут указывать не только на то, что произошла ошибка, но и на то, какой бит вызвал ошибку.

Хэмминг изучил существующие схемы кодирования, включая две из пяти, и обобщил их концепции. Для начала он разработал номенклатуру для описания системы, включая количество битов данных и битов исправления ошибок в блоке. Например, четность включает в себя один бит для любого слова данных, поэтому, предполагая ASCII слова с семью битами, Хэмминг описал это как код (8,7), всего восемь битов, из которых семь являются данными. Пример повторения будет (3,1), следуя той же логике. Кодовая скорость - это второе число, деленное на первое, для нашего примера с повторением 1/3.

Хэмминг также заметил проблемы с переворачиванием двух или более битов и описал это как «расстояние» (теперь оно называется расстоянием Хэмминга, после него). Четность имеет расстояние 2, поэтому одно переключение бита можно обнаружить, но не исправить, и любые два изменения бита будут невидимы. Повторение (3,1) имеет расстояние 3, так как три бита необходимо перевернуть в одной и той же тройке, чтобы получить другое кодовое слово без видимых ошибок. Он может исправлять однобитовые ошибки или обнаруживать, но не исправлять, двухбитовые ошибки. Повторение (4,1) (каждый бит повторяется четыре раза) имеет расстояние 4, поэтому переворот трех битов можно обнаружить, но не исправить. Когда три бита в одной группе меняются местами, могут возникнуть ситуации, когда попытка исправить приведет к неправильному кодовому слову. Как правило, код с расстоянием k может обнаруживать, но не исправлять k - 1 ошибок.

Хэмминга интересовали сразу две проблемы: как можно больше увеличить расстояние и в то же время как можно больше увеличить скорость кода. В 1940-х годах он разработал несколько схем кодирования, которые значительно улучшили существующие коды. Ключом ко всем его системам было перекрытие битов четности, чтобы им удавалось проверять друг друга, а также данные.

Общий алгоритм

Следующий общий алгоритм генерирует код исправления одиночных ошибок (SEC) для любого количества битов. Основная идея состоит в том, чтобы выбрать биты с исправлением ошибок так, чтобы индекс-XOR (XOR всех битовых позиций, содержащих 1) был равен 0. Мы используем позиции 1, 10, 100 и т. Д. ( в двоичном формате) в качестве битов исправления ошибок, что гарантирует возможность установки битов исправления ошибок так, чтобы индекс-исключающее ИЛИ всего сообщения был равен 0. Если получатель получает строку с индексом-исключающее ИЛИ 0, он может заключить повреждений не было, в противном случае индекс-XOR указывает индекс поврежденного бита.

Алгоритм может быть выведен из следующего описания:

Пронумеруйте биты, начиная с 1: бит 1, 2, 3, 4, 5, 6, 7 и т. Д.
Запись номера битов в двоичном формате: 1, 10, 11, 100, 101, 110, 111 и т. д.
Все позиции битов, которые являются степенями двойки (имеют один бит 1 в двоичной форме их позиции) являются битами четности: 1, 2, 4, 8 и т. д. (1, 10, 100, 1000)
Все остальные битовые позиции, с двумя или более 1 битами в двоичной форме их позиции, являются данными биты.
Каждый бит данных включен в уникальный набор из 2 или более битов четности, что определяется двоичной формой его битовой позиции.
1. Бит четности 1 охватывает все битовые позиции, для которых установлен наименьший значащий бит: бит 1 (сам бит четности), 3, 5, 7, 9 и т. Д.
2. Бит четности 2 охватывает все позиции битов, для которых установлен второй младший значащий бит: бит 2 (сам бит четности), 3, 6, 7, 10, 11 и т. Д.
3. Бит четности 4 охватывает все позиции битов, для которых установлен третий младший значащий бит: биты 4–7, 12–15, 20–23 и т. Д.
4. Бит четности 8 охватывает все биты позиции, в которых установлен четвертый младший значащий бит: биты 8–15, 24–31, 40–47 и т. д.
5. Как правило, каждый бит четности охватывает все биты, для которых выполняется побитовое И позиция четности и позиция бита не равны нулю.

Если байт данных, который должен быть закодирован, равен 10011010, то слово данных (с использованием _ для представления битов четности) будет __1_001_1010, а кодовое слово - 011100101010.

Выбор четности, четной или нечетной, не имеет значения, но один и тот же выбор должен использоваться как для кодирования, так и для декодирования.

Это общее правило можно показать визуально:

Биты кодированных данных		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Положение бита		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
Четность. бит. охват	p1
	p2
	p4
	p8
	p16

Показаны только 20 закодированных битов (5 четности, 15 данных), но шаблон продолжается бесконечно. Ключевой особенностью кодов Хэмминга, которую можно увидеть при визуальном осмотре, является то, что любой заданный бит включен в уникальный набор битов четности. Чтобы проверить наличие ошибок, проверьте все биты четности. Шаблон ошибок, называемый синдромом ошибки , определяет бит с ошибкой. Если все биты четности верны, ошибки нет. В противном случае сумма позиций ошибочных битов четности идентифицирует ошибочный бит. Например, если биты четности в позициях 1, 2 и 8 указывают на ошибку, то бит 1 + 2 + 8 = 11 является ошибочным. Если только один бит четности указывает на ошибку, сам бит четности ошибочен.

Как видите, если у вас есть m битов четности, он может охватывать биты от 1 до $2 m - 1 {\ displaystyle 2 ^ {m} -1}$ $2 ^ {m} -1$ . Если вычесть биты четности, у нас останется $2 m - m - 1 {\ displaystyle 2 ^ {m} -m-1}$ $2 ^ мм-1$ бит, которые мы можем использовать для данных. При изменении m мы получаем все возможные коды Хэмминга:

Биты четности	Всего битов	Биты данных	Имя	Скорость
2	3	1	Хэмминга (3,1). (Triple код повторения )	1/3 ≈ 0,333
3	7	4	Хэмминга (7,4)	4/7 ≈ 0,571
4	15	11	Хэмминга(15,11)	11/15 ≈ 0,733
5	31	26	Хэмминга (31,26)	26/31 ≈ 0,839
6	63	57	Хэмминга(63,57)	57/63 ≈ 0,905
7	127	120	Hamming(127,120)	120/127 ≈ 0,945
8	255	247	Hamming(255,247)	247 / 255 ≈ 0,969
…
m	$n = 2 м - 1 {\ displaystyle n = 2 ^ {m} -1}$ ${\ displaystyle n = 2 ^ {m} -1}$	$k = 2 m - m - 1 {\ displaystyle k = 2 ^ {m} -m-1 }$ $k=2^{m}-m-1$	Хэмминга $(2 м - 1, 2 м - м - 1) {\ displaystyle (2 ^ {m} -1,2 ^ {m} -m-1)}$ $(2 ^ m-1,2 ^ mm-1)$	$(2 м - m - 1) / (2 m - 1) {\ displaystyle (2 ^ {m} -m-1) / (2 ^ {m} -1)}$ $(2 ^ m - m - 1) / (2 ^ m-1)$

Коды Хэмминга с дополнительной четностью (SECDED)

Коды Хэмминга имеют минимальное расстояние 3, что означает, что декодер может обнаруживать и исправлять одиночную ошибку, но не может отличить двойную битовую ошибку некоторого кодового слова от одиночной битовой ошибки другого c. одесловие. Таким образом, некоторые двухбитовые ошибки будут неправильно декодированы, как если бы они были одноразрядными ошибками, и, следовательно, останутся необнаруженными, если не будет предпринята попытка исправления.

Чтобы исправить этот недостаток, коды Хэмминга могут быть расширены дополнительным битом четности. Таким образом, можно увеличить минимальное расстояние кода Хэмминга до 4, что позволяет декодеру различать одиночные битовые ошибки и двухбитовые ошибки. Таким образом, декодер может обнаруживать и исправлять одиночную ошибку и в то же время обнаруживать (но не исправлять) двойную ошибку.

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

Этот расширенный код Хэмминга популярен в системах памяти компьютеров, где он известен как SECDED (сокращенно от «исправление одиночных ошибок», «обнаружение двойных ошибок»). Особенно популярен код (72,64), усеченный (127,120) код Хэмминга плюс дополнительный бит четности, который имеет такие же объемы служебных данных, как и код четности (9,8).

[7,4] Код Хэмминга

Графическое изображение четырех битов данных и трех битов четности и какие биты четности применяются к каким битам данных

В 1950 году Хэмминг представил [7,4] Код Хэмминга. Он кодирует четыре бита данных в семь битов, добавляя три бита четности. Он может обнаруживать и исправлять однобитовые ошибки. С добавлением общего бита четности он также может обнаруживать (но не исправлять) двухбитовые ошибки.

Построение G и H

Матрица $G: = (I k - AT) {\ displaystyle \ mathbf {G}: = {\ begin {pmatrix} {\ begin {array} {c | c} I_ {k} - A ^ {\ text {T}} \\\ end {array}} \ end {pmatrix}}}$ ${\ mathbf {G}}: = {\ begin {pmatrix} {\ begin {array} {c | c} I_ {k} - A ^ {{\ text {T}}} \\\ end {array}} \ конец {pmatrix}}$ называется (каноническим) образующая матрица линейного (n, k) кода,

и $H: = (AI n - k) {\ displaystyle \ mathbf {H}: = {\ begin {pmatrix} {\ begin {array} {c | c} A I_ {nk} \\\ end {array}} \ end {pmatrix}}}$ ${\ mathbf {H}}: = {\ begin {pmatrix} {\ begin {array} {c | c} AI _ {{nk}} \\\ end {array}} \ end {pmatrix}}$ называется матрицей проверки на четность.

Это конструкция из G и H в стандартной (или систематической) форме. Независимо от формы, G и H для линейных блочных кодов должны удовлетворять

$HGT = 0 {\ displaystyle \ mathbf {H} \, \ mathbf {G} ^ {\ text {T}} = \ mathbf {0}}$ ${\ mathbf {H}} \, {\ mathbf {G}} ^ {{\ text {T}}} = { \ mathbf {0}}$ , матрица из нулей.

Поскольку [7, 4, 3] = [n, k, d] = [2 - 1, 2−1 − m, 3]. Матрица проверки на четность Hкода Хэмминга строится путем перечисления всех столбцов длины m, которые попарно независимы.

Таким образом, H - это матрица, левая часть которой представляет собой все ненулевые наборы из n элементов, где порядок наборов из n элементов в столбцах матрицы не имеет значения. Правая часть - это просто (n - k) - единичная матрица.

Итак, G может быть получена из H путем транспонирования левой части H с единичной k- единичной матрицей в левой части G.

Код образующей матрицы $G {\ displaystyle \ mathbf {G }}$ $\ mathbf {G}$ и матрица проверки на четность $H {\ displaystyle \ mathbf {H}}$ $\ mathbf {H}$ :

$G: = (1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1) 4, 7 {\ displaystyle \ mathbf {G}: = {\ begin {pmatrix} 1 0 0 0 1 1 0 \\ 0 1 0 0 1 0 1 \\ 0 0 1 0 0 1 1 \\ 0 0 0 1 1 1 1 \\\ end {pmatrix}} _ {4,7}}$ $\ mathbf {G}: = \ begin {pmatrix} 1 0 0 0 1 1 0 \\ 0 1 0 0 1 0 1 \\ 0 0 1 0 0 1 1 \\ 0 0 0 1 1 1 1 \\ \ end {pmatrix} _ {4,7}$

$H: = (1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1) 3, 7. {\ displaystyle \ mathbf {H}: = {\ begin {pmatrix} 1 1 0 1 1 0 0 \\ 1 0 1 1 0 1 0 \\ 0 1 1 1 1 0 0 1 \\\ end {pmatrix}} _ {3,7}.}$ $\ mathbf {H}: = \ begin {pmatrix} 1 1 0 1 1 0 0 \\ 1 0 1 1 0 1 0 \ \ 0 1 1 1 0 0 1 \\ \ end {pmatrix} _ {3,7}.$

Наконец, эти матрицы можно преобразовать в эквивалентные несистематические коды с помощью следующих операций:

Перестановки столбцов (замена столбцов)
Операции с элементарными строками (замена строки линейной комбинацией строк)

Кодирование

Пример

Из вышеприведенной матрицы имеем 2 = 2 = 16 кодовых слов. Пусть $a → {\ displaystyle {\ vec {a}}}$ ${\ vec {a}}$ будет вектор-строкой бит двоичных данных, $a → = [a 1, a 2, a 3, a 4 ], ai ∈ {0, 1} {\ displaystyle {\ vec {a}} = [a_ {1}, a_ {2}, a_ {3}, a_ {4}], \ quad a_ {i} \ in \ {0,1 \}}$ ${\ displaystyle {\ vec {a}} = [a_ {1 }, a_ {2}, a_ {3}, a_ {4}], \ quad a_ {i} \ in \ {0,1 \}}$ . Кодовое слово $x → {\ displaystyle {\ vec {x}}}$ ${\ vec {x}}$ для любого из 16 возможных векторов данных $a → {\ displaystyle {\ vec {a}}}$ ${\ displaystyle {\ vec {a}}}$ задается стандартным матричным произведением $x → = a → G {\ displaystyle {\ vec {x}} = {\ vec {a}} G}$ $\ vec { x} = \ vec {a} G$ , где операция суммирования выполняется по модулю 2.

Например, пусть $a → = [1, 0, 1, 1] {\ displaystyle {\ vec {a}} = [1,0,1,1]}$ ${\ displaystyle {\ vec {a}} = [1,0,1,1]}$ . Используя образующую матрицу $G {\ displaystyle G}$ $G$ сверху, мы имеем (после применения по модулю 2 к сумме)

$x → = a → G = (1 0 1 1) (1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1) = (1 0 1 1 2 3 2) = (1 0 1 1 0 1 0) {\ displaystyle {\ vec {x}} = {\ vec {a}} G = {\ begin {pmatrix} 1 0 1 1 \ end {pmatrix}} {\ begin {pmatrix} 1 0 0 0 1 1 0 \\ 0 1 0 0 0 1 0 1 \\ 0 0 1 1 0 0 0 0 1 \\ 0 0 1 1 0 0 0 0 0 1 \\ 0 0 1 1 0 0 0 0 0 0 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 1 0 1 1 2 3 2 \ end {pmatrix}} = {\ begin {pmatrix} 1 0 1 1 0 1 0 \ end {pmatrix}}}$ ${\vec {x}}={\vec {a}}G={\begin{pmatrix}1011\end{pmatrix}}{\begin{pmatrix}1000110\\0100101\\0010011\\0001111\\\end{pmatrix}}={\begin{pmatrix}1011232\end{pmatrix}}={\begin{pmatrix}1011010\end{pmatrix}}$

[7,4] Код Хэмминга с дополнительным бит четности

Тот же [7,4] пример выше с дополнительным битом четности. Эта диаграмма не предназначена для соответствия матрице H.

Код Хэмминга [7,4] можно легко расширить до кода [8,4], добавив дополнительный бит четности поверх (7, 4) закодированное слово (см. Хэмминга (7,4) ). Это можно суммировать с помощью исправленных матриц:

G: = (1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0) 4, 8 {\ displaystyle \ mathbf {G}: = {\ begin {pmatrix} 1 1 1 0 0 0 0 1 \\ 1 0 0 1 1 1 0 0 1 \\ 0 1 0 1 0 1 0 1 \\ 1 1 0 1 0 0 0 1 0} \ end {p : = (1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1) 4, 8. {\ displaystyle \ mathbf {H}: = {\ begin {pmatrix} 1 0 1 0 1 0 1 0 \\ 0 1 1 0 0 1 1 0 \\ 0 0 0 1 1 1 1 1 0 \\ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 \ end _ {424>}. форма. Чтобы получить G, можно использовать элементарные операции со строками для получения матрицы, эквивалентной H в систематической форме:

H = (0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1) 4, 8. {\ displaystyle \ mathbf {H} = \ left ({\ begin {array} {cccc | cccc} 0 1 1 1 1 0 0 0 \\ 1 0 1 1 0 1 0 0 \\ 1 1 0 1 0 0 0 1 0 \\ 1 1 1 0 1 \ end массив) {0} {0}

{\ mathbf {H}} = \ left ({\ begin {array} {cccc | cccc} 0 1 1 1 1 0 0 0 \\ 1 0 1 1 1 0 1 0 0 \\ 1 1 0 1 0 0 1 \\ 1 1 1 0 0 0 0 1 \ end {array}} \ right) _ {{4,8 }}.

Например, первая строка в этой матрице представляет собой сумму второй и третьей строк H в несистематической форме. Используя приведенную выше систематическую конструкцию для кодов Хэмминга, матрица A очевидна, а систематическая форма G записывается как

G = (1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 0) 4, 8. {\ displaystyle \ mathbf {G} = \ left ({\ begin {array} {cccc | cccc} 1 0 0 0 0 1 1 1 1 \\ 0 1 0 0 1 0 1 1 \\ 0 0 1 0 1 1 0 0 1 \\ 0 0 0 1 1 end array. {} {}

{\ mathbf {G}} = \ left ({\ begin {array} {cccc | cccc} 1 0 0 0 0 1 1 1 \\ 0 1 0 0 1 0 1 1 \\ 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 array}} \ right) _ {{4,8}}.

Несистематическая форма G может быть сокращена по строке (с использованием элементарных операций со строкой), чтобы соответствовать этой матрице.

Добавление четвертой строки эффективно вычисляет сумму всех битов кодового слова (данные и четность) как четвертый бит четности.

Например, 1011 кодируется (с использованием несистематической формы G в начале этого раздела) в 01100110, где синие цифры - данные; красные цифры - это биты четности из кода Хэмминга [7,4]; а зеленая цифра - это бит четности, добавленный кодом [8,4]. Зеленая цифра делает четность кодовых слов [7,4] четной.

Наконец, можно показать, что минимальное расстояние увеличилось с 3 в коде [7,4] до 4 в коде [8,4]. Следовательно, код можно определить как [8,4] код Хэмминга.

Чтобы декодировать код Хэмминга [8,4], сначала проверьте бит четности. Если бит четности указывает на ошибку, исправление одиночной ошибки (код Хэмминга [7,4]) укажет местоположение ошибки, а «нет ошибки» указывает бит четности. Если бит четности правильный, то исправление одиночной ошибки укажет (побитовое) исключающее ИЛИ из двух местоположений ошибок. Если местоположения равны («нет ошибки»), то двойная битовая ошибка либо не произошла, либо исчезла сама собой. В противном случае произошла двойная битовая ошибка.

См. Также

Примечания

Ссылки

Внешние ссылки