Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 23
Текст из файла (страница 23)
Однако в случае, когда испорчена только одна строка, ее можно восстановить, складывая строки поразрядно по правилу ИСКЛЮЧАЮЩЕЕ ИЛИ, опустив при этом поврежденную строку, но принимая во внимание строку контрольных битов по столбцам. 94 Глава 2. Числовые системы и коды (а) Строки являются кодовыми словами кода С Столбцы (с) Строки яшмются климы. ми слолаии с одним контрольным битом проверки на яеляются кодоеыми словами кода С„, (Ь) условия четности по строкам не нарушены Сюлбцы являются кодоеыми снопами с одним контрольным битом прюеим на явность Услояия четности по столбцам не нарушены Рис.
2.14. Двумерные коды: (а) общая структура; (ь) код с проверкой иа чет- ность в строках и столбцах с минимальным расстоянием, равным 4; (с) типичная конфигурация необнаруживаемых ошибок Чтобы получить еще большее минимальное расстояние, в отношении строк и/или столбцов можно применить код Хэмминга с минимальным расстоянием 3 или 4. Можно также построить кодс ббльшим числом измерений и минимальным расстоянием, равным произведению минимальных расстояний в каждом измерении.
Важным применением двумерных кодов являются запоминающие устройства типа /тА/О (Кот(цпт(апт Аггау оГ !п скрепа!уе Р)з)са, набор недорогих дисков с избыточностью). В таком устройстве используются тгь! дисков для хранения данных, объем которых соответствует емкости и дисков. Например, восемь 8-гигабайтовых дисковых накопителей можно использовать для хранения 64 гигабайтов данных без избыточности, а девятый 8-гигабайтовый диск мог бы служить для записи проверочной информации На рис. 2.15 схематически изображен двумерный код для системы йА1Р, каждый дисковый накопитель считается строкой кода. В каждом накопителе сохраняются и блоков данных, содержащих обычно по 512 байтов.
В частности, на 8-гига- байтовом диске можно запомнить около 16 миллионов блоков Как показано на рисунке, каждый блок включает свои собственные проверочные биты, образуемые по правилу циклического кода, чтобы обнаруживать ошибки внутри блока. В первых л накопителях хранятся данные без избыточности Каждый блок(пч-!)-го накопителя содержит контрольные биты для соответствующих битов первых и и акопителей Это означает, что т-й бит и Ь-м блоке на (ич-1)-м диске выбирается так, чтобы число единиц в т-х разрядах Ь-х блоков на всех дисках было четным 2.15.
Коды, обнаруживающие и исправляющие оциибки 95 Ноыкр блоко 1 2 9 Я 5 6 и 6 9161112 Диск ! диск 2 Диск 3 диск 4 Диск 5 ди12 б ы данныи 2 з Я 5 6 и 512 СНС блок Диск и ДНО! ЛЯ! Рис. 2. ! 5. Структура кода, исправляющего ошибки, для системы ВА!О (СВС— проверочные биты циклического кода) В процессе работы ошибки в информационных битах обнаруживаются циклическим кодом. В любом случае, когда обнаружена ошибка в блоке на одном из дисков, правильное содержимое этого блока можно получить путем простой проверки на четность соответствующих блоков на всех других дисках, включая (пэ1)-й.
И хотя зто требует п дополнительных чтений с дисков, это все же лучше, чем потерять ваши данные! При записи нового информационного блока также требуются дополнительные обращения к дискам для обновления соответствующего проверочного блока(см. задачу 2.46) Поскольку обычно записи происходят значительно реже, чем чтения, эти «накладные» расходы не обременительны.
2.15.6. Коды с контрольной суммой Операция проверки на четность, о которой говорилось в предыдущих разделах, является по существу сложением битов по модулю 2: сумма набора битов по модулю 2 равна О, если число единиц в этом наборе четно, н равна 1, если оно нечетно. Правило сложения по модулю можно распространить на другие основания, отличающиеся от 2, и таким образом получать проверочные цифры В компьютерах, например, данные хранятся в виде совокупности 8-битовых. байтов. Можно считать, что каждый байт имеет десятичное значение от О до 255.
Поэтому для образования проверки по байтам можно воспользоваться сложением по модулю 256 Одиночный проверочный байт, являющийся суммой по модулю 256 всех информационных байтов, называется ~онтрольной суммой (си!вонзит) Получающийся в результате код с контрольной суммой (си!осилит сок(в) может обнаружить любую одиночную ошибку в байте, поскольку такая ошибка приведет к расхождению между вновь вычисленной суммой байтов и контрольной суммой Для построения кодов с контрольной суммой при сложении можно использовать и другие модули. Важными, в частности, являются коды с контрольной суммой, которую находят путем сложения по модулю 255, то есть коды с контр о кь ной суммой, образуемой путны сложения в обратном коде (опвз'-сотр!етеп! сйвскзит сок(вз); такие коды обладают особыми свойствами в отношении вычисленийй н обнаружения ошибок, в связи с чем эти коды применяются для защиты от ошибок в загыовках пакетов в вездесущем протоколе Интернета (1 пгегпет ртогосо1, 1Р; см.
Обзор литературы). ьзп Глава 2. Числовые системы и коды 2.15.7. Коды «тизл» Минимальное расстояние в кодах «1 нз л» и «а из л», введенных в параграфе 2.13, равно 2, поскольку изменение только одного бита изменяет число единиц в кодовом слове н приводит, таким образом, к слову, не являющемуся кодовым. Эти коды обладают другим полезным свойством с точки зрения обнаружения ошибок: они обнаруживают множественные однонаправленные ошибки. Под однонаправленной ошибкой (ипп!ггесг!опа! еггог) понимают случай, когда изменение во всех ошибочных битах происходит в одну сторону (нулн изменяются на единицы или наоборот). Это свойство оказывается очень полезным, если преобладающий механизм ошибок в системе имеет тенденцию изменять все биты в одну и ту же сторону.
2.16. Коды для последовательной передачи и хранения данных 2.16.1. Параллельное и последовательное представление данных В большинстве компьютеров и в других цифровых системах данные передаются н хранятся в параллельном формате (рсгайе! да!а), При параллельной передаче данных для каждого бита в слове данных предоставлена отдельная сигнальная линия. При параллельном хранении данных все биты словаданных можно записать и прочитать одновременно. В некоторых приложениях применение параллельных форматов не оправдывает затрат. Например, для параллельной передачи байтов данных по телефонной сети потребовалось бы восемь телефонных линий, а для параллельного хранения байтов данных на магнитном диске нужно было бы иметь накопитель с восемью отдельными головками для чтения/записи.
Пса««до«ательлые форматы (лена! На!а) позволяют передавать данные, а также записывать и считывать их при хранении по одному биту зараз, благодаря чему стоимость системы во многих случаях снижается. Рис.2.16 является иллюстрацией основных идей, относящихся к посл едо вател ьной передаче данных, Периодическим тактовым сигналом СЫСК задается скорость передачи битов: по одному биту за период тактового сигнала. Таким образом, скорость передачи, измеряемая числом дивов в секунду (бит!с; Ь!! гаге, Ьрз), равна частоте тактового сигнала, выраженной числом периодов в секунду (герп, Гц). Величина, обрапил скорости передачи (выраженной в бит!с)„называется длительностью бата (Ьй Ите); численно она равна периоду тактового сигнала в секундах (с). Это время отводится в линии посл сдователь ной передач и данных (названной на рисунке ЗЕВОТА) на каждый передаваемый бит.
Иногда время, занимаемое каждым битом, называют битовой ячейкой (Ьп се!!). Фактический вид сигнала, возникающего в линии в пределах каждой ячейки, зависит от сигнального кода (!!пе сог)е), В случае простейшего сигнального кода, называемого кодам без вт«рата к нулю ( топ-йегп~.п-го-_#_ею, ФРД, единичный бит передается путем удерживания на линии 1 в течение всего времени, занимаемого битовой ячейкой, а 2. 16. Коды для последовательной передачи и х ранения данных 97 нулевой бит — путем передачи О. В следующем разделе обсуждаются более сложные сигнальные колы, реализующие другие правила.
время С'кОСК ЯЕПСАТА Рис. 2.16. Основные понятия, относящиеся к последовательной передаче данных Независимо от сигнального кода, в системах с последовательной передачей данных или с последовательными записью н чтением данных прн их хранении бывает необходим какой-то способ указания на роль каждого бита в последовательном потоке. Предположим, например, что последовательно передаются 8-битовые байты. Как узнать, какой бнт является первым в каждом байте? Необходимую информацию несет смгпав сипхропизамии (зупсгагопишаоп и8паГ), названный ЯМЧС парис.
2.16. Он равен 1 только на первом бите каждого байта. Очевидно, что для приема потока последовательно передаваемых данных нам нужны три сигнала: тактовый сигнал для определения границ битовых ячеек, си гнал синхронизации для определения границ между словами и сами данные, передаваемые последовательно. В ряде приложений, в частности, в линиях связи межлу блоками в компьютере нли между узлами в телекоммуникационной системе каждый из этих сигналов передается по отдельному проводу; сокращение числа проводов до 3-х вместо п дает большую экономию.
Пример системы с 3-проводнойй последовательной передачей данных будет приведен в разделе 8.5.4, Во многих случаях стоимосп передачи трех отдельных сигналов оказывается все же слишком высокой (например, стоимость трех телефонных ливий или трех головок чтения/записи). Тогда все три сигнала объединяются в один последовательный поток данных и применяются сложные аналоговые и цифровые схемы для извлечения из потока данных тактового сигнала и сигнала синхронизации.
*2.16.2. Сигнальные коды для последовательной передачи Чаще всего для последовательной передачи данных используется один из сигнальных кодов, приведенных на рнс.2.17. В коде МкХ значение каждого бита посылается по линии в течение всего времени, занимаемого битовой ячейкой. Это простейшее и самое надежное правило кодирования для передачи на короткие расстояния. Однако обычно требуется одновременно с данными посылать тактовый сигнал, задающий положение битовых ячеек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
