Э. Таненбаум - Архитектура компьютера (1127755), страница 23
Текст из файла (страница 23)
Если байты нумеру)отея слева направо, биты 110 находятся в байте 3 (или 7, или 11 и т. д.). Если байты нумеруются справа налево, биты 110 находятся в байте 0 (или 4, или 8 и т. д.). В обеих системах слово, содержащее это целое число, имеет адрес О. Если компьютеры содержат только целые числа, никаких сложностей не возникает. Однако многие прикладные задачи требуют использования не только целых чисел, но и цепочек символов и других типов данных.
Рассмотрим, например, простую запись данных о персонале, состоящую из строки (имя сотрудника) и двух целых чисел (возраст и номер отдела). Строка завершается одним или несколькими нулевыми байтами, призванными заполнить слово целиком. На рис. 2.10, а для записи «)пп Впп(Ь, 21 год, отдел 260» (1 х 256 е 4 = 260) представлена схема с нумерацией байтов справа налево, а на рис. 2.10, б — с нумерацией байтов слева направо. Основная память 91 Оба этих представления хороши и внутренне последовательны. Проблемы начинаются тогда, когда один из компьютеров пытается переслать запись на другой компьютер по сети.
Предположим, что машина с нумерацией байтов слева направо пересылает запись на компьютер с нумерацией байтов справа налево по одному байту, начиная с байта 0 и заканчивая байтом 19. Для простоты будем считать, что биты не инвертируются при передаче. Таким образом, байт 0 переносится из первой машины на вторую в байт 0 и т. д., как показано на рис. 2.10, в. Компьютер, получивший запись, имя печатает правильно, но возраст получается 21 х 2", и номер отдела тоже искажается. Такая ситуация возникает, поскольку при передаче записи порядок следования букв в слове меняется так, как нужно, но при этом порядок следования байтов в целых числах тоже меняется, что приводит к неверному результату. Очевидное решение проблемы — использование программы, которая инвертировала бы байты в слове после создания копии.
Результат такой операции представлен на рис. 2.10, а Мы видим, что числа стали правильными, однако строка превратилась в «М!)Т1МВ>, при этом буква «Н» вообще расположилась отдельно. Строка переворачивается потому, что компьютер сначала считывает байт 0 (пробел), затем байт 1 (М) и т, д.
Простого решения не существует. Есть один способ, но он неэффективен. (Нужно перед каждой единицей данных помещать заголовок, информирующий, какой тип данных следует за ним — строка, целое и т. д. Это позволит компьютеру-получателю производить только необходимые преобразования.) Ясно, что отсутствие стандарта упорядочивания байтов является главным неудобством при обмене информацией между разными машинами.
Код исправления ошибок Память компьютера из-за всплесков напряжения и по другим причинам время от времени может ошибаться. Чтобы бороться с ошибками, используются специальные коды, умеющие обнаруживать и исправлять ошибки. В этом случае к каждому слову в памяти особым образом добавляются дополнительные биты. Когда слово считывается из памяти, эти дополнительные биты проверяются, что и позволяет обнаруживать ошибки. Чтобы понять, как обращаться с ошибками, необходимо внимательно изучить, что представляют собой этн ошибки. Предположим, что слово состоит из и бит данных, к которым мы дополнительно прибавляем г бит (контрольных разрядов).
Пусть общая длина слова составит п бит (то есть и = лг + г). Единицу из п бнт, содержащую т бит данных и г контрольных разрядов, часто называют кодовым словом. Для любых двух кодовых слов, например 10001001 и 10110001, можно определить, сколько соответствующих битов в них различаются. В данном примере таких бита три. Чтобы определить количество различающихся битов, нужно над двумя кодовыми словами произвести логическую операцию ИСКЛЮЧАЮЩЕЕ ИЛИ и сосчитать количество битов со значением 1 в полученном результате. Число битовых позиций, по которым различаются два слова, называется интервалом Хэмминга 185~.
Если интервал Хэмминга для двух слов равен г1, значит, 92 Глава 2. Организация компьютерных систем что достаточно Ы битовых ошибок, чтобы превратить одно слово в другое. Например, интервал Хэмминга для кодовых слов 11110001 и 00110000 равен 3, поскольку для превращения первого слова во второе достаточно 3 битовые ошибки. Память состоит из т-разрядных слов, следовательно, существуют 2ь вариантов сочетания битов. Кодовые слова состоят из и бит, но из-за способа подсчета контрольных разрядов допустимы только 2 из 2" кодовых слов. Если в памяти обнаруживается недопустимое кодовое слово, компьютер знает, что произошла ошибка. При наличии алгоритма подсчета контрольных разрядов можно составить полный список допустимых кодовых слов, и из этого списка найти два слова, для которых интервал Хэмминга будет минимальным.
Это интервал Хэмминга для полного кода. Возможности проверки и исправления ошибок определенного кода зависят от его интервала Хэмминга. Чтобы обнаружить г1 ошибок в битах, необходим код с интервалом И + 1, поскольку Ы ошибок не могут превратить одно допустимое кодовое слово в другое допустимое кодовое слово. Соответственно, чтобы исправить г( ошибок в битах, необходим код с интервалом 2Ы + 1, поскольку в этом случае допустимые кодовые слова настолько сильно отличаются друг от друга, что, даже если произойдет г1 изменений, изначальное кодовое слово окажется ближе к ошибочному, чем любое другое кодовое слово, поэтому его без труда можно будет выявить.
В качестве простого примера кода с обнаружением ошибок рассмотрим код, в котором к данным присоединяется один бит четности. Бит четности выбирается таким образом, чтобы число битов со значением 1 в кодовом слове было четным (или нечетным). Интервал Хэмминга для этого кода равен 2, поскольку любая одиночная битовая ошибка приводит к кодовому слову с неправильной четностью. Другими словами, достаточно двух одиночных битовых ошибок для перехода от одного допустимого кодового слова к другому допустимому слову. Такой код может использоваться для обнаружения одиночных ошибок.
Если из памяти считывается слово с неверной четностью, поступает сигнал об ошибке. Программа не сможет выполняться, но зато не выдаст неверных результатов. В качестве простого примера кода исправления ошибок рассмотрим код с четырьмя допустимыми кодовыми словами: 0000000000, 0000011111, 1111100000 и 1111111111. Интервал Хэмминга для этого кода равен 5.
Это значит, что он может исправлять двойные ошибки. Если появляется кодовое слово 0000000111, компьютер знает, что изначально это слово выглядело как 0000011111 (если произошло не более двух ошибок). При появлении трех ошибок (например, слово 0000000000 меняется на 0000000111) этот метод не подходит. Представим, что мы хотим разработать код, в котором и бит данных и г контрольных разрядов, позволяющий исправлять все одиночные битовые ошибки. Каждое из 2 допустимых слов имеет п недопустимых кодовых слов, которые отличаются от допустимого одним битом. Они образуются инвертированием каждого из п бит в п-разрядном кодовом слове.
Следовательно, каждое из 2 допустимых слов требует и + 1 возможных сочетаний битов, приписываемых этому слову (и возможных ошибочных вариантов и один правильный). Поскольку общее число различных сочетаний битов равно 2", то (и + 1) 2ь < 2". Так как и = т + г, Основная память 93 то (т е г е 1) < 2". Эта формула дает нижний предел числа контрольных разря- дов, необходимых для исправления одиночных ошибок.
В табл. 2.2 показано не- обходимое количество контрольных разрядов для слов разного размера. Таблица 2.2. Число контрольных разрядов для кода, способного исправлять одиночные ошибки Размер исходного Количество Общий размер Процент слова контрольных разрядов олова увеличения слова 12 50 21 31 19 16 32 38 64 71 !36 128 256 265 1О 522 512 А шибко Биты четности Рис. 2.1 1. Кодирование числа 1100 (а); добавляются биты четности (б); ошибка в секторе АС (з) Далее мы добавим бит четности к каждому из трех пустых секторов, чтобы сумма битов в каждом из трех кругов, А, В, и С, получилась четной, как показано на рис. 2.11, б.
В круге А находится 4 числа: О, О, 1 и 1, которые в сумме дают четное число 2. В круге В находятся числа 1, 1, 0 и О, которые также при сложении дают четное число 2. Аналогичная ситуация и для круга С. В данном примере получилось так, что все суммы одинаковы, но вообще возможны случаи с суммами 0 и 4. Рисунок соответствует кодовому слову, состоящему из 4 бит данных и 3 бит четности. Этого теоретического нижнего предела можно достичь, используя метод Ричарда Хзмминга 185). Но прежде, чем обратиться к указанному алгоритму, давайте рассмотрим простую графическую схему, которая четко иллюстрирует идею кода исправления ошибок для 4-разрядных слов. Диаграмма Венна на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
