Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 20
Текст из файла (страница 20)
Используются только шесть из восьми возможных 3- разрядных кодовых слов, и соответствие межлу шестью выбранными кодовыми словамии и состояниями светофора произвольно, так что кодирование можно осуществить многими способами. Опытный разработчик цифровых устройств выбирает способ кодирования так, чтобы минимизировать стоимость схемы или оптимизировать какой-нибудыйзугой параметр (например, время разработки: нет необходимости перебирать миллиарды возможных вариантов кодирования). Табл. 2.12. Состояния контроллера светофора Сигналы светофора И-3 И-3 Звлв- Жвлна~й тый И-З Е-Я Е-ИГ Крис- Зеле- Жвлный ный гый Е- Я Кодовое Крае- слово ный Состояние К-В проезд разрешен И-Я приготовиться К-В проезд запрещен Е-(т' проезд разрешен Е-% приготовиться Е-% проездзапрещен ВКЛ.
выкн. выкл. выкл. выкл. выкл. ВКЛ. выкл. выкл. выкл. ВКЛ. 000 ВКЛ. 001 ВКЛ. 010 выкл. 100 выкл. 101 ВКЛ. ! 10 ВКЛ, выкл. выкл. ВКЛ. ВКЛ. выкл выкл. выкл. выкл. выкл. выкл, выкл. ВКЛ. выкл. ВКЛ. выкл. выкл. ВКЛ. выкл, выкл. Другое применение двоичного кода иллюстрирует рис. 2.7(а). В изображенной здесь системе имеется и устройств, каждое из которых может выполнять определенное действие. Характеристики этих устройств таковы, что они могут быть доступны для управления ими только поодиночке. Блок управления вырабатывает слово двоичного кода «выбор устройства», состоящее из Ь = ! 1он,п ~ битов, для того чтобы указать, к какому устройству он обращается в тот или иной момент времени. Кодовое слово «выбор устройства» поступает на все устройства, каждое нз которых сравнивает его со своим собственным «удостоверением личности», чтобы определить, происходит ли обращение именно к нему.
Хотя число битов в кодовых словах двоичного кода минимально, выбор двонч ного кода не всегда я ел яется лучшим для кодирования действий, условий или состояний. На рис. 2.7(Ь) показано, как можно управлять п устройствами с помощью п-разрядного кода «1 из п» (!-оиг-о(-'п сок(е), в словах которого только один бит равен 1, а остальные равны О. Каждый бит в слове кода «1 из п» непосредственно подается на вхол разрешения соответствующего устройства. Зто упрощает конструкцию устройств, поскольку им больше не нужно распознавать обращение к себе; все, что нужно устройству, — это одноразрядный вход «разрешения».
Кодовые слова кода«1 из 10» были приведены в табл. 2 9, Иногда слово, состоящее из всех нулей, также может входить в код «! нз 10», чтобы указывать, что никакое устройство не выбирается. Другим употребительным кодом является об- 82 Глава2. Числовыесиствыы и коды ратный код «1 из п» (гптеггег( 1-ои1-о~-'и сод«); входящие в него кодовые слова имеют один нулевой бит, а все остальные биты равны 1.
Рис. 2.7. Схема управления для цифровой системы си устройствами: (в) с использованием двоичного кода (де»(се 1() — идентификатор устройства); (Ь) с использованием кода 1 из и» В сложных системах мажет применяться комбинация различных методов кодирования. Рассмотрим, например, систему, подобную приведенной на рис. 2.71Ь), в которой каждое из и устройств содержит до «узлов.
В этом случае кодовое слово, вырабатываемое блоком управления, может состоять из двух полей: поля выбора устройства, формируемого по принципу «1 из и», и состоящего из й = ( (оя «! битов поля выбора одного из я узлов внутри данного устройства, формируемого по правилам двоичного кода. Обобщением кода «1 из и» является код «т нз п» (т-о«до~ и сог(е), в кодовых словах которого т битов равны 1, а все остальные биты равны О. Слово кода «т из п» можно распознать с помощью логической схемы И с т входами, на выходе которой единичное значение возникает только тогда, когда на все ее входы поданы 1. Сделать это довольно просто и недорого, однако в большинстве случаев значения т таковы, что число кодовых слов в коде «т из п» много больше, чем число слов в коде «1 из п». Полное число кодовых слов выражается биномиальным 1 и ) и( коэффициентом ~ ~, Равным 1(и т), .
Таким обРазом, код «2 из 4» состоит из б кодовых слов, а код «3 из 10» содержит 120 слов. 2.14. л-мерныа кубы и расстояние 83 *2.14. и-мерные кубы и расстояние Строку из и битов можно интерпретировать геометрически как вершину объекта, называемого и-мерным кубан (п-сиЬе). На рис. 2.8 представлены и-мерные кубы для п = 1, 2, 3, 4. У и-мериого куба имеется 2" вершин, каждая из которых помечена строкой из п битов.
Изображенные на рисунке ребра показывают, что у каждой вершины есть и смежных с нею вершин, метки которых отличаются от метки данной вершины только одним битом. Нарисовать и-мерный куб для п бол ыпе 4 весьма затруднительно. 10 11 Ф ° е ° 00 01 ~ ° 0 1 Одномерный куб Двумерный куб 1110 1111 11О 111 010 1101 Трекмерный куб 4-мерный куб Рис. 2.8. л-мерные кубы для и = 1, 2, 3 и 4 Понятие и-мерного куба при разумных значениях и позволяет мысленно представить себе, в чем состоят проблемы кодирования и минимизации логических схем. Например, задача о построении и-разрядиого кода Грея эквивалентна нахождению пути по ребрам и-мерного куба, на котором каждая вершина посещается точно один раз.
Такие пути для 3- н 4-разрядных кодов Грея показаны на рис.2.9. Важным частным случаем кода «и из п» является код ЯВ10В (ВВ!ОВ со<ке), используемый в гигабнтном стандарте Ебзегпе1 802.3з. В этом коле имеется 256 десятиразрядных двоичных кодовых слов, каждое из которых может служить для представления данных, выражаемых 8-ю битами. Большая часть кодовых слов гзо~ является кодом «5 из 10», Однако, поскольку 1, ) равно всеголишь 252, использованы также некоторые слова кодов «4 из 10» и «6 из 1О», дополняющие код до нужного числа кодовых слов, причем осуществлено это весьма интересным способом, о чем подробнее будет рассказано в разделе 2.16,2. 84 Глава 2.
Числовые системы и кодьз 1110 1111 ° . ° оыо . ------ .. --Р~ .' Ю11,' 011 1Ц30., 110 111 ° — ° 1101 1001 1О! — ° 000 001 (е) (!з) Рмс. 2.9. Перемещение по и-мерному кубу в порядке, задаваемом кодом Грея: (в) 3-мерный куб; (Ы 4-мериый куб Кубы дают возможность геометрически интерпретировать понятие расстояния (йвгапсв), называемого также расстоянием Хэммиига (Оатт!пя йвзапсе). Расстояние между двумя п-разрядными строками — это число разрядов, в которых эти строки различаются. В геометрической интерпретации расстояние — это минимальная длина пути между двумя соответствующими вершинами, Расстояние между двумя смежными вершинами равно1; расстояние между вершинами 3-мерного куба 001 и 100 равно 2.
Понятие расстояния является ключевым для понимания и построения кодов, исправляющих ошибки, которым посвящен следующий параграф. Рассмотрим множество, состоящее из 2 вершин и-мерного куба, у каждой из которых п-т битов имеют одинаковые значения, а в остающихся т разрядах перебираются все возможные2 комбинаций; такое множество называется т-мерныи поднубом (т-виЬсиЬе) п-мерного куба.
Например, вершины (000, О!О, 100, 110) образуют 2-мерный подкуб 3-мерного куба. Такой подкуб можно записать в виде одной строки: ххО, где «х» означает бизп с безразличным значвнисмз (акоп 1-саге); данному подкубу принадлежат все вершины с одинаковыми битами в разрядах, не обозначенных знаком «х». Как мы увидим в параграфе 4.4, понятие подкубов особенно полезно для мысленного представления того, как действуют алгоритмы минимизации стоимости комбинационных логических схем.
*2.15 Коды, обнаруживающие и исправляющие ошибки Под тиибкой (взтог) в цифровой системе понимают искажение данных, в результате чего их правильные значения теряются. Ошибка бывает вызвана физической неисправностью ~а!! иге). Неисправности могут быть временными (гетрогагу) или постоянны»ш (рвгтапвш). Например, космические лучи или поток альфа- частиц могут вызвать временный отказ блока памяти, изменив какой-нибудь бит из числа хранящихся в нем. Перегрев схемы или разряд статического электричества могут привести к постоянной неисправности, в результате чего этот узел никогда не будет функционировать правильно, 2.15.
Коды, обнаруживающие и исправляющие ошибки 85 2.16.1. Коды, обнаруживающиеошибки Вспомним, что согласно определению, данному в параграфе 2.10, код, состоящий из п-разрядных двоичных строк, не обязательно содержит все возможные 2" кодовых слов; это как раз тот случай, о котором сейчас пойдет речь. Код, обнаруживающий ошибки (еггаг-г!вг«сттй саде), обладает тем свойством, что в результате искажения или повреждения кодового слова вероятнее всего получится двоичная строка, не явлнющансл кодовым словам (папсайв и агд). Если в системе используется код, обнаруживающий ошибки, то в ней генерируются, передаются и запоминаются только кодовые слова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
