Электроника:Цифровая электроника/Принципы цифровых вычислений/Таблицы поиска

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Перевод: Макаров В. (valemak) Контакты:</br>* Habr: @vakemak</br>* Сайт: www.valemak.com</br>Перевёл статей: 656.
Проверка/Оформление/Редактирование: Мякишев Е.А.


Таблицы поиска[1]

Познакомившись с цифровыми устройствами памяти в предыдущей главе, мы теперь знаем, что можно хранить двоичные данные в твердотельных устройствах. Эти «ячейки» хранения в твердотельных запоминающих устройствах легко адресуются, управляя «адресными» линиями устройства с правильным двоичным значением (или значениями).

Предположим, у нас есть схема памяти ПЗУ, записанная или запрограммированная с определёнными данными, так что адресные строки ПЗУ служат входами, а линии данных ПЗУ служат выходами, генерируя характеристический ответ конкретной логической функции. Теоретически мы могли бы запрограммировать эту микросхему ПЗУ для эмуляции любой логической функции, которую захотим, без необходимости изменять какие-либо проводные соединения или вентили.

Рассмотрим следующий пример ПЗУ размером 4 × 2 бита (очень маленькая память!), запрограммированного на функцию полусумматора:

Рис. 1. ПЗУ размером 4 × 2 бита, запрограммированное на функцию полусумматора.
Рис. 1. ПЗУ размером 4 × 2 бита, запрограммированное на функцию полусумматора.

Если это ПЗУ записано с указанными выше данными (представляющими таблицу истинности полусумматора), управление адресными входами A и B вызовет активацию соответствующих ячеек памяти в микросхеме ПЗУ, что приведёт к выводу соответствующих данных в виде бит на Σ (сумма) и CВых.. В отличие от схемы полусумматора, состоящей из вентилей или реле, это устройство можно настроить для выполнения любой логической функции с двумя входами и двумя выходами, а не только функции полусумматора.

Чтобы изменить логическую функцию, всё, что нужно сделать, это записать другую таблицу данных в другую микросхему ПЗУ. Мы могли бы даже использовать чип EPROM, который можно было бы перезаписывать по желанию, обеспечивая максимальную гибкость в работе.

Критично важно осознавать значение этого принципа применительно к цифровым схемам. В то время как полусумматор, построенный из вентилей или реле, обрабатывает входные биты, чтобы получить определённый выход, ПЗУ просто запоминает, какими должны быть выходы для любой заданной комбинации входов.

Это мало чем отличается от «таблиц умножения», заученных в начальной школе: вместо того, чтобы вычислять произведение 5 на 6 (5 + 5 + 5 + 5 + 5 + 5 = 30), школьников учат запоминать, что «пятью шесть равно тридцать», а затем при более сложных расчётах использовать это произведение по памяти по мере необходимости. Точно так же логическая функция зависит не от функционального устройства жёстко запрограммированных вентилей или реле (аппаратное обеспечение), а исключительно от данных, записанных в память (программное обеспечение).

Такое простое приложение с определёнными выходами для каждого входа называется таблицей поиска, потому что запоминающее устройство просто «ищет», какими должны быть выходные данные для любой заданной комбинации входных состояний.

Такое применение запоминающего устройства для выполнения логических функций важно по нескольким причинам:

  • Программное обеспечение гораздо легче изменить, чем аппаратное.
  • Программное обеспечение может быть заархивировано на различных типах носителей памяти (диск, лента), что обеспечивает простой способ документирования и управления функцией в «виртуальной» форме; оборудование может быть «заархивировано» только абстрактно в виде какого-то графического рисунка (схемы).
  • Программное обеспечение можно копировать с одного устройства памяти (например, микросхемы СППЗУ) на другое, что позволяет одному устройству «научить» своей функции другое устройство.
  • Программное обеспечение, такое как пример логической функции, может быть разработано для выполнения функций, которые было бы чрезвычайно трудно эмулировать с помощью дискретных логических вентилей (или реле!).

Полезность таблиц поиска становится всё более и более очевидной с увеличением сложности функции. Предположим, мы хотим построить схему 4-битного сумматора с использованием ПЗУ. Нам потребуется ПЗУ с 8 адресными строками (два 4-битных числа, которые нужно сложить вместе) плюс 4 строки данных (обозначены для вывода):

Рис. 2. ПЗУ с 8 адресными строками плюс 4 строки данных.
Рис. 2. ПЗУ с 8 адресными строками плюс 4 строки данных.

С 256-ю адресуемыми ячейками памяти в этой микросхеме ПЗУ нам пришлось бы достаточно много программировать, сообщая, какой двоичный вывод генерировать для каждой комбинации двоичных входов.

Мы также рискуем допустить ошибку в нашем программировании и получить неправильную сумму, если не проявим повышенную бдительность. Однако гибкость настройки этой функции (или любой другой функции) только с помощью программного обеспечения, как правило, перевешивает эти затраты.

Рассмотрим некоторые расширенные функции, которые мы могли бы реализовать с помощью вышеуказанного «сумматора». Мы знаем, что, когда мы складываем два набора чисел в нотации c дополнением до двух, мы рискуем в ответе получить переполнение.

Например, если мы попытаемся сложить 0111 (десятичное число 7) с 0110 (десятичное число 6) только с 4-битным числовым полем, мы получим 1001 (десятичное число -7) вместо правильного значения, 13 (7 + 6), что не может быть выражено с помощью только 4 битов со знаком. Если бы мы захотели, мы могли бы избежать странных ответов, выдаваемых при переполнении, запрограммировав эту схему таблицы поиска так, чтобы она выдавала что-то ещё в условиях, когда мы знаем, что произойдет переполнение (то есть в любом случае, когда реальная сумма превысит +7 или -8).

Одной из альтернатив может быть программирование ПЗУ для вывода количества 0111 (максимальное положительное значение, которое может быть представлено 4 знаковыми битами) или любого другого значения, которое мы определили как более подходящее для приложения, чем типичное «ошибочное» переполнение, что будет выводить обычная сумматорная схема. Программист должен решить, что он (или она) хочет, чтобы эта схема делала, потому что мы больше не ограничены ограничениями функций логических элементов.

Возможности не ограничиваются индивидуальными логическими функциями. Добавив больше адресных строк в микросхему ПЗУ 256 × 4, мы можем расширить таблицу поиска, включив в неё несколько функций:

Рис. 3. Расширенная таблица поиска.
Рис. 3. Расширенная таблица поиска.

С двумя дополнительными адресными линиями микросхема ПЗУ будет иметь в 4 раза больше адресов, чем раньше (1024 вместо 256). Это ПЗУ можно было запрограммировать так, чтобы, когда A8 и A9 были «низкими», выходные данные представляли собой сумму двух 4-битных двоичных чисел, введённых в адресные линии от A0 до A7, точно так же, как мы делали с предыдущей схемой ПЗУ 256 × 4.

Для адресов A8 = 1 и A9 = 0 можно запрограммировать вывод разницы (вычитания) между первым 4-битным двоичным числом (от A0 до A3) и вторым двоичным числом (от A4 до A7). Для адресов A8 = 0 и A9 = 1 мы могли бы запрограммировать ПЗУ на вывод разности (вычитания) двух чисел в обратном порядке (второе → первое, а не первое → второе) и, наконец, для адресов A8 = 1 и A9 = 1, ПЗУ можно запрограммировать на сравнение двух входных данных и вывод индикации равенства или неравенства.

Тогда у нас будет устройство, способное выполнять четыре различных арифметических операции над 4-битными двоичными числами, все путём «поиска» запрограммированных в нём ответов.

Если бы мы использовали микросхему ПЗУ с более чем двумя дополнительными адресными линиями, мы могли бы запрограммировать её с более широким набором функций для выполнения на двух 4-битных входах. Существует ряд операций, характерных для двоичных данных (таких как проверка чётности или «Исключающее ИЛИ» для битов), которые мы могли бы найти полезными для программирования в подобной таблице поиска.

Такие устройства, которые могут выполнять различные арифметические задачи в соответствии с двоичным входным кодом, известны как арифметико-логические устройства (АЛУ) и составляют один из важнейших компонентов компьютерной технологии. Хотя современные АЛУ чаще строятся из очень сложных комбинационных логических (вентильных) схем из соображений быстродействия, должно быть приятно осознавать, что точно такая же функциональность может быть продублирована с помощью «тупой» микросхемы ПЗУ, запрограммированной с помощью соответствующей таблицы (или таблиц) поиска.

Фактически, именно этот подход был использован инженерами IBM в 1959 году при разработке компьютеров IBM 1401 и 1620, в которых для выполнения сложения использовались таблицы поиска, а не схема двоичного сумматора. Машину ласково называли «CADET» («КАДЕТ»), что означало «Can’t Add, Doesn’t Even Try» («Не могу добавить, даже не пытаюсь»).

Очень распространённое применение ПЗУ с таблицами поиска – в системах управления, где необходимо представить пользовательскую математическую функцию. Такое применение можно найти в управляемых компьютером системах впрыска топлива для автомобильных двигателей, где надлежащее соотношение воздушно-топливной смеси для эффективной и чистой работы изменяется в зависимости от нескольких экологических и эксплуатационных переменных.

Испытания, проведённые на двигателях в исследовательских лабораториях, определяют, каковы эти идеальные соотношения для различных условий нагрузки двигателя, температуры окружающего воздуха и атмосферного давления. Переменные измеряются датчиками, их аналоговые выходные сигналы преобразуются в цифровые с помощью аналого-цифровой схемы, а эти параллельные цифровые сигналы используются в качестве входных адресов для микросхемы ПЗУ большой ёмкости, запрограммированной на вывод оптимального цифрового значения соотношения воздух/топливо для любого из этих заданных условий.

Иногда ПЗУ используются для предоставления функций одномерной таблицы поиска для «корректировки» оцифрованных значений сигналов, чтобы они более точно отображали их реальное значение. Примером такого устройства является датчик термопары, который измеряет сигнал в милливольтах, генерируемый соединением разнородных металлов, и выдаёт сигнал, который, как предполагается, непосредственно соответствует температуре этого соединения.

К сожалению, спаи термопар не имеют идеально линейных характеристик температура/напряжение, поэтому необработанный сигнал напряжения не полностью пропорционален температуре. Оцифровывая сигнал напряжения (аналого-цифровое преобразование) и отправляя это цифровое значение по адресу ПЗУ, запрограммированного с необходимыми значениями коррекции, программирование ПЗУ может устранить некоторую нелинейность отношения температуры термопары к милливольтам, так что окончательный вывод устройства будет более точным.

Популярный инструментальный термин для такой таблицы поиска – цифровой характеризатор.

Рис. 4. Цифровой характеризатор.
Рис. 4. Цифровой характеризатор.

Ещё одно применение таблиц поиска – специальный перевод кода. Например, ПЗУ 128 × 8 можно использовать для преобразования 7-битного кода ASCII в 8-битный код EBCDIC:

Рис. 5. Преобразование 7-битного кода ASCII в 8-битный код EBCDIC.
Рис. 5. Преобразование 7-битного кода ASCII в 8-битный код EBCDIC.

Опять же, всё, что требуется – это правильно запрограммировать микросхему ПЗУ необходимыми данными, чтобы каждый действительный ввод ASCII производил соответствующий выходной код EBCDIC.

См.также

Внешние ссылки