Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 22
Текст из файла (страница 22)
2.15. Коды, обнаруживающие и исправляющие оыаибки 89 l ;.",. и.:, 10100011 3: ': ""! .~-;.'~.:, "'-~~,г;: (а) , 00100011 11100011 "-;;.;"'~~~и)«(г,',:;-' Ошибке (Ь) „;;,:'1-"Ч:.о:1,:.'.,,".-~;:,, 00101010 11010011:::Е',::,,'а»,г,.,»;,'., 10100011 ч ',: ",'" ';" ° ".''е р тройная оомби ": г-Т,т '« ";::!~:;;!:,::":;: " аыгащит аа одиночная Г . '' 0010101! е ° ° ° 11000011 ~.~ ~г.. одиночные, двойные и !родные ооибаи (с) Рис. 2.12.
Кодовые слова и слова, не являюшиеся кодовыми, для 8-разрядного двоичного кода с минимальным расстоянием, равным ий (а) исправлениеодиночных и обнаружение двойных ошибок; (Ь) ошибочное «исправление» тройной ошибки; (с) отказ от исправления ошибок взамен обнаружения до 3-х ошибок 90 Глава 2. Числовые системы и коды Номер разряда 7 5 5 4 3 2 1 Имя ~руппы Группы Проверочные бити НОмер разгара 7 6 5 3 4 2 1 имя в группы Группы Информацяонные биты Проверочные биты Рис. 2.1 3.
Проверочные матрицы для 7-разрядного кода Хзмми ига: 1а) с Распо- ложением битов в порядке следования их номеров; 1Ь1 с разделением прове- рочных и информационных битов По традиции разряды в проверочной матрице и в самих кодовых словах бывают переставлены таким образом, чтобы все проверочные биты оказывались справа, как показано парис. 2 13(Ь). В первых двух столбцах табл.2.14 перечислены получающиесяя в результате этого кодовые слова. Можно быть уверенным в том, что минимальное расстояние в коде Хэмминга равно 3, если в любом кодовом слове необходимо изменить, по крайней мере, 3 бита, чтобы получить другое кодовое слово. Другими словами, нужно убедиться в том, что изменение одного бита или двух битов в кодовом слове дает слово, не являющееся кодовым.
Если изменить один бит вяцм разряде кодового слова, то нарушится условие четности в каждой из групп, в которую входит/-й разряд. Поскольку каждый информационный бит содержится, хотя бы в одной группе, как минимум в одной из групп условие четности не будет выполнено и получающееся в результате слово не является кодовым. Что произойдет, если мы изменим два бита ваьм и А-м разрядах? В тех контрольных группах, которые содержат оба эти разряда, условие четности останется по- прежнему верным, поскольку оно не нарушается при изменении четного числа битов. Поскольку, однако, 7 и А различны, их выражения в двоичной записи отличаются, по крайней мере, в одном бите, соответствующем одной из контрольных групп.
В этой группе изменится только один бит, в результате чего условие четности окажется невыполненным и получившееся слово не будет кодовым, 2.15. Коды, обнаруживающие и исправляющие ошибки 91 Табл. 2.14. Кодовые слова кодов Хзмминга с четырьмя информационными би- тами с минимальными расстояниями, равными 3 и 4 Код с минимальным расстоянием 3 Код с минимальным рвсстсвннвм 4 Инфсрмвциснные биты Проверочные биты Проверочные биты Информационные биты 0000 000 0000 0000 01! 0001 О!!! 0001 00!О 101 0010 1011 0011 1!О 00!! 1100 110! !10 0100 0100 101 0101 10!О 0101 О!10 01!О О!1 0110 0111 000 0111 0001 1110 1000 1000 1001 100 1001 1001 О!01 1010 010 !010 1011 !011 0010 001! 1!00 0100 1101 1101 010 1000 11!О !00 1110 !111 1!! 1111 1!11 Если вы понимаете зто доказательство, то вам нетрудно увидеть, что правила нумерации разрядов, принятые при построении кода Хэмминга, являются простым следствием того, что содержится в приведенном рассуждении.
В первой части доказательства (ошибки в одном бите) мы потребовали, чтобы ни олин номер разряда не был равен нулю. А во второй части доказательства (ошибки в двух битах) мы потребовали, чтобы никакие два разряда не имели одинаковых номеров.
Таким образом, если номера разрядов записываются ! битам н, то можно построить код Хэмминга с числом разрядов до 2'-1. Доказательство указывает также, как можно построить декодер, исправляющий ошибки (еггаг-саггесблй бесаг1ег) в принимаемых словах кода Хэмминга. Прежде всего проверяются условия четности во всех контрольных группах; если все условия четности выполнены, то принятое слово считается правильным, Если в одной группе или в большем числе групп условие четности нарушено, то счита- Табл.2.15.
Числсразрядов вксдсвыхслсвахкодсвХзммингас минимальными расстояниями, равными 3 и 4 Код е минимальным расстояниям 4 Код е минимальным расстоянием 3 Ипформациоп- пыа бвгы Проверочные биты 2 Общее число бугов Проверочные Общее число биты битов <4 <15 <2б <3! <б4 < !20 < !2Я < !27 2. 1 5.4. ЦИК21ИЧЕОКИ8 КОД!я! Помимо кодов Хэмминга придумано много других кодов, обнаруживающих н исправляющих ошибки. Самыми важными являются циктпчсские коды [сусбсге<!ипг2апсу-сйес1г [СРС) со!гез), которые, как это нн странно, включают в себя ется, что произошла одиночная ошибка. Совокупность групп с нечетным числом единиц [называемая синдромом [зупй отеЯ должна иметь один общий столбец в проверочной матрице; предполагается, что значение соответствующего разряда неверно и оно заменяется на противоположное.
Предположим, например, что используется код, указанный на рис.2. 13[Ь) и принято слово 0101011. Число единиц в группах В и С нечетно, что соответствует 6-му разряду в проверочной матрице (синдром равен 11О, то есть 6). Беря обратное значение бита в 6-м разряде, мы найдем правильноеслово;0001011, Код Хэмминга с минимальным расстоянием 3 легко видоизменить так, чтобы увеличить минимальное расстояние и сделать его равным 4. Просто добавляется еше один проверочный бит, значение которого выбирается таким, чтобы полное число единиц во всех разрядах, включая новый бит, было четным.
Как и в коде с одним контрольным символом и проверкой на четность, этот бит гарантирует, что все ошибки, возникающие в нечетном числе разрядов, будут обнаруживаться. В частности, обнаруживаются все тройные ошибки. Мы уже показали, что все одиночные и двойные ошибки обнаруживаются другими проверочными битами, поэтому минимальное расстояние модифицированного кода должно равняться 4. Коды Хэмминга с минимальным расстоянием, равным 3 и 4, широко применяются для обнаружения и исправления ошибок в запоминающих системах компьютеров, в частности, в больших универсальных вычислительных машинах, где на запоминающие устройства приходится основная масса системных отказов.
Эти коды особенно привлекательны, когда длина запоминаемых слов очень велика, поскольку требуемое число проверочных битов растет медленно с увеличением длины слова, как показано в табл.2.15. 2.15. Коды,обнаруживающиеиисправляющие ошибки 93 коды Хэмминга. Существует развитая теория этих кодов, посвященная не только их способности обнаруживать и исправлять ошибки, но и позволяющая строить для них недорогие кодеры и декодеры (см. Обзор литературы).
Двумя важными приложениями циклических кодов является их использование в дисковых накопителях и в сетях передачи данных. Каждый блок данных на диске (обычно 512 байтов) защищен циклическим кодом, так что ошибки внутри блока могут быть обнаружены, а в некоторых случаях и исправлены. В сетях передачи данных кшкдый пакет данных заканчивается проверочными битами циклического кода. Именно циклические коды были выбраны для этих двух применений из-за их способности обнаруживать пачки ошибок. Кроме одиночных ошибок они могут обнаруживать многократные ошибки, которые образуют компактные группы в блоке данных на диске или в пакете.
Такие ошибки более вероятны, чем ошибки, равномерно распределенные по разрядам, так как наиболее вероятные причины ошибок в этих двух применениях — это дефекты поверхности дисков и всплески шума в каналах связи. 2.15.5. Двумерные коды Другой способ получения кода с большим минимальным расстоянием заключается в построении двумерного кода (гг«о-Йпгепзйопа! сог1«), иллюстрацией чего служит рис. 2.14(а).
Из информационных битов образуется двумерная решетка и проверочные биты добавляются как к строкам, так и к столбцам. Для строк используется код С с минимальным расстоянием Ы, а для столбцов — возможно гого гоо' другой код С, с минимальным расстоянием Ы ы Другими словами, проверочные символы строки выбираются так, чтобы каждая строка была кодовым словом кода С, а проверочные символы столбца-так, чтобы каждый столбец был кодовым словом кода С и 1Проверочные биты в «углу» решетки можно выбрать сосог гласно одному из этих кодов.) Минимальное расстояние в двумерном коде равно произведению Ы и гт,; в связи с этим двумерный код иногда называют кодомгов соГ п1гоизведение»г [ргогзасГ соде).
В двумерном коде, показанном парне.2.14(Ь), для строк и столбцов используются коды с одним контрольным символом проверки на четность, так что минимальное расстояние в двумерном коде равно 2.2 = 4. Мы можем легко убедиться в этом, проверив, что любая комбинация из одной, двух или трех ошибок в битах приведет к нарушению условия четности в строке или в столбце или в том и другом.
Чтобы ошибкабыла необнаруживаемой, необходимо изменить, по меньшей мере, четыре бита, расположенные по углам прямоугольника, как показано на рис.2. 14(с). Процедура обнаружения и исправления ошибок этим кодом носит совершенно естественный характер. Предположим, что мы считываем информацию по строке за рвз. Прочтя каждую строку, мы проверяем ее принадлежность строковому коду. Если в строке обнаруживается ошибка, то только по виду этой строки мы еще не можем сказать, какой бит неверен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
