(926)274-88-54
Бесплатная доставка.
Бесплатная сборка.
График работы:
Ежедневно. С 8-00 до 20-00.
Почта: soft_hous@mail.ru
|
|
Звоните! (926)274-88-54 Бесплатная доставка. Бесплатная сборка. |
Ассортимент тканей График работы: Ежедневно. С 8-00 до 20-00. Почта: soft_hous@mail.ru |
  
|
Читальный зал --> Программные средства foundation Код с минимальным расстоянием 3 Код с минимальным расстоянием 4
Если вы понимаете это доказательство, то вам нетрудно увидеть, что правила нумерации разрядов, принятые при построении кода Хэмминга, являются простым следствием того, что содержится в приведенном рассуждении. В первой части доказательства (ошибки в одном бите) мы потребовали, чтобы ни один номер разряда не был равен нулю. А во второй части доказательства (ошибки в двух битах) мы потребовали, чтобы никакие два разряда не имели одинаковых номеров. Таким образом, если номера разрядов записываются / битами, то можно построить код Хэмминга с числом разрядов до 2-1. Доказательство указывает также, как можно построить декодер, исправляющий ошибки (error-correcting decoder) в принимаемых словах кода Хэмминга. Прежде всего проверяются условия четности во всех контрольных группах; если все условия четности выполнены, то принятое слово считается правильным. Если в одной группе или в большем числе групп условие четности нарушено, то счита- Табл. 2.14. Кодовые слова кодов Хэмминга с четырьмя информационными битами с минимальными расстояниями, равными 3 и 4 -----------------------. пт ется, что произошла одиночная ошибка. Совокупность фупп с нечетным числом единиц [называемая синдромом (syndrome)] должна иметь один общий столбец в проверочной матрице; предполагается, что значение соответствующего разряда неверно и оно заменяется на противоположное. Предположим, например, что используется код, указанный на рис. 2. ] 3(b) и принято слово 0101011. Число единиц в группах В и С нечетно, что соответствует б-му разряду в проверочной матрице (синдром равен 110, то есть 6). Беря обратное значение бита в 6-м разряде, мы найдем правильное слово: 0001011. Код Хэмминга с минимальным расстоянием 3 легко видоизменить так, чтобы увеличить минимальное расстояние и сделать его равным 4. Просто добавляется еще один проверочный бит, значение которого выбирается таким, чтобы полное число единиц во всех разрядах, включая новый бит, было четным. Как и в коде с одним контрольным символом и проверкой на четность, этот бит гарантирует, что все ошибки, возникающие в нечетном числе разрядов, будут обнаруживаться. В частности, обнаруживаются все тройные ошибки. Мы уже показали, что все одиночные и двойные ошибки обнаруживаются другими проверочными битами, поэтому минимальное расстояние модифицированного кода должно равняться 4. Коды Хэмминга с минимальным расстоянием, равным 3 и 4, широко применяются для обнаружения и исправления ошибок в запоминающих системах компьютеров, в частности, в больших универсальных вычислительных машинах, где на запоминающие устройства приходится основная масса системных отказов. Эти коды особенно привлекательны, когда длина запоминаемых слов очень велика, поскольку требуемое число проверочных битов растет медленно с увеличением длины слова, как показано в табл. 2.15. Табл. 2.15. Число разрядов в кодовых словах кодов Хэмминга с минимальными расстояниями, равными 3 и 4 Код с минимальным Код с минимальным Информацион- расстоянием 3 расстоянием 4 ные биты Проверочные Общее число Проверочные Общее число биты битов биты битов
2.15.4. Циклические коды Помимо кодов Хэмминга придумано много других кодов, обнаруживающих и исправляющих ошибки. Самыми важными являются циклические коды [cyclic-redundancy-check (CRC) codes], которые, как это ни странно, включают в себя коды Хэмминга. Существует развитая теория этих кодов, посвященная не только их способности обнаруживать и исправлять ошибки, но и позволяющая строить для них недорогие кодеры и декодеры (см. Обзор литературы). Двумя важными приложениями циклических кодов является их использование в дисковых накопителях и в сетях передачи данных. Каждый блок данных на диске (обычно 512 байтов) защищен циклическим кодом, так что ошибки внутри блока могут быть обнаружены, а в некоторых случаях и исправлены. В сетях передачи данных каждый пакет данных заканчивается проверочными битами циклического кода. Именно циклические коды были выбраны для этих двух применений из-за их способности обнаруживать пачки ошибок. Кроме одиночных ошибок они могут обнаруживать многократные ошибки, которые образуют компактные группы в блоке данных на диске или в пакете. Такие ошибки более вероятны, чем ошибки, равномерно распределенные по разрядам, так как наиболее вероятные причины ошибок в этих двух применениях - это дефекты поверхности дисков и всплески шума в каналах связи. 2.15.5. Двумерные коды Другой способ получения кода с большим минимальным расстоянием заключается в построении двумерного кода {two-dimensional code), иллюстрацией чего служит рис. 2.14(a). Из информационных битов образуется двумерная решетка и проверочные биты добавляются как к строкам, так и к столбцам. Для строк используется код С с минимальным расстоянием d, а для столбцов - возможно другой код Ci с минимальным расстоянием d Другими словами, проверочные символы строки вь[бираются так, чтобы каждая строка была кодовым словом кода С а проверочные символы столбца-так, чтобы каждый столбец был кодовым словом кода Cj. (Проверочные биты в углу решетки можно выбрать согласно одному из этих кодов.) Минимальное расстояние в двумерном коде равно произведению d и d-, в связи с этим двумерный код иногда называют кодом-произведением (product code). В двумерном коде, показанном нарис. 2.14(b), для строк и столбцов используются коды с одним контрольным символом проверки на четность, так что минимальное расстояние в двумерном коде равно 22 = 4. Мы можем легко убедиться в этом, проверив, что любая комбинация из одной, двух или трех ошибок в битах приведет к нарушению условия четности в строке или в столбце или в том и другом. Чтобы ошибка была необнаруживаемой, необходимо изменить, по меньшей мере, четыре бита, расположенные по углам прямоугольника, как показано на рис. 2.14(c). Процедура обнаружения и исправления ошибок этим кодом носит совершенно естественный характер. Предположим, что мы считьшаем информацию по строке за раз. Прочтя каждую строку, мы проверяем ее принадлежность строковому коду. Если в строке обнаруживается ошибка, то только по виду этой строки мы еще не можем сказать, какой бит неверен. Однако в случае, когда испорчена только одна строка, ее можно восстановить, складывая строки поразрядно по правилу ИСКЛЮЧАЮЩЕЕ ИЛИ, опустив при этом поврежденную строку, но принимая во внимание строку контрольных битов по столбцам. ООО «Мягкий Дом» - это Отечественный производитель мебели. Наша профильная продукция - это диваны еврокнижка. Каждый диван можем изготовить в соответствии с Вашими пожеланияи (размер, ткань и материал). Осуществляем бесплатную доставку и сборку. Звоните! Ежедневно! (926)274-88-54 Продажа и изготовление мебели. Копирование контента сайта запрещено. Авторские права защищаются адвокатской коллегией г. Москвы. |