Разработка простых цифровых устройств

Простейшим путем построения подобного преобразователя является использование приоритетных шифраторов (рис. 14.2).

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

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

Наиболее универсальная схема преобразователя, легко наращиваемая и достаточно простая, приведена на рис. 14.3.

Для опроса коммутационной матрицы применяется счетчик, тактируемый генератором. Старшие разряды счетчика используются для выбора одной из строк матрицы с помощью дешифратора (на выбранную строку поступает сигнал логического нуля, на невыбранную — сигнал логической единицы). Младшие разряды счетчика используются для опроса столбцов матрицы с помощью мультиплексора. Сигнал с опрашиваемого столбца подается на выход мультиплексора. Признаком нажатия клавиши является нулевой сигнал на выходе мультиплексора. В этот момент на выходах счетчика присутствует код номера нажатой клавиши. Такая схема легко позволяет строить клавиатуры на большое количество клавиш (до 256, как на рисунке, и даже больше), однако она требует довольно большого времени для полного опроса клавиатуры (так как количество тактов опроса равно полному количеству клавиш).

Совмещение двух рассмотренных подходов позволяет создавать достаточно большие клавиатуры с малыми аппаратурными затратами и малым временем опроса.

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

В нашем случае клавиатура имеет 128 клавиш, то есть коммутационная матрица должна состоять из 16 строк, опрашиваемых дешифратором 4–16 (ИД3), и 8 столбцов, сигналы с которых обрабатываются шифратором 8–3 (ИВ1). Счетчик должен иметь 4 разряда (ИЕ7). Эти 4 разряда и 3 разряда с выхода шифратора дадут 7-разрядный номер нажатой клавиши. Полный цикл опроса клавиатуры будет занимать 16 тактов генератора (по числу строк). Признаком нажатия одной из клавиш будет отрицательный сигнал на выходе –GS шифратора. Если нажато несколько клавиш в разных строках, то обрабатываться будет та клавиша, строка которой будет опрошена первой. Если нажато несколько клавиш в одной строке, то шифратор выдаст код клавиши, соответствующей большему номеру входа. Надо также учитывать, что шифратор ИВ1 выдает инверсный номер входа, на который пришел нулевой сигнал, — эта особенность может потребовать применения трех выходных инверторов (на рисунке не показаны).

Оценим, какой должна быть частота тактового генератора. Мы приняли, что максимальная скорость нажатия равна 20 раз в секунду. Значит, за 1/20 секунды надо успеть опросить всю клавиатуру, то есть все 16 строк. Таким образом, минимально допустимая тактовая частота составляет 16•20 = 320 Гц. Но надо заложить и запас на обработку дребезга контактов. Поэтому примем тактовую частоту опроса равной 400 Гц. Она может быть и больше, но чрезмерно увеличивать ее (например, выше 1 кГц) не стоит, так как при быстром переключении микросхем увеличивается потребляемый схемой ток. Понятно, что генератор должен быть не кварцевым, так как кварцевые резонаторы на низкие частоты не выпускаются, а делитель частоты резко усложнит схему. К тому же точная выдержка частоты генератора в данном случае совершенно не нужна.

Выходной сигнал "–Нажатие", конечно же, будет иметь короткие паразитные импульсы. Во-первых, они будут возникать из-за дребезга контактов нажатой в данный момент клавиши. Во-вторых, они могут появляться из-за переходных процессов при переключении счетчика и дешифратора. Эти паразитные импульсы надо исключать.

Чтобы исключить действие паразитных импульсов из-за переходных процессов при переключении счетчика и дешифратора достаточно применить стробирование или тактирование сигнала "–Нажатие" в середине каждого тактового интервала. Для этого из схемы преобразователя надо вывести сигнал "–Такт".

Исключение коротких выходных импульсов из-за дребезга контактов клавиш сложнее. Прежде всего, на время нажатия клавиши целесообразно остановить опрос строк с помощью сигнала "–Запрет". Затем надо обработать сигнал "?Нажатие" по принципу, показанному на рис. 14.1. Будем считать, что при дребезге контактов длительность кратковременного размыкания не превышает периода тактового генератора (2,5 мс при тактовой частоте 400 Гц). Тогда задержка окончания сигнала флага нажатия (см. рис. 14.1) должна быть не менее одного периода тактового сигнала. Для выработки задержки можно использовать цепочку триггеров, тактируемых сигналом "–Такт".

Схема выработки выходных сигналов клавиатуры приведена на рис. 14.5.

Триггер Т1 перебрасывается в единицу (на инверсном выходе) тогда, когда в середине тактового интервала (по положительному фронту сигнала "–Такт") сигнал "–Нажатие" нулевой. Своим выходным сигналом триггер Т1 перебрасывает в единицу триггер Т2, который уже никак не связан с сигналом "–Нажатие", не реагирует ни на какой дребезг этого сигнала. Выходной сигнал триггера Т2 используется в качестве сигнала флага нажатия клавиатуры. Инверсный сигнал с выхода триггера Т2 используется в качестве сигнала "–Запрет", останавливающего опрос строк клавиатуры.

Цепочка триггеров Т3 и Т4, тактируемая сигналом "Такт", служит для задержки снятия сигнала флага после отпускания клавиши (когда сигнал "–Нажатие" становится равным единице). После установки флага в единицу, сигнал флага начинает записываться по фронту сигнала "–Такт" в триггеры Т3 и Т4, но только в том случае, когда сигнал "–Нажатие" установлен в единицу. В результате на инверсном выходе триггера Т4 появится сигнал логического нуля при нахождении сигнала "–Нажатие" в единице в моменты двух последовательных положительных фронтов сигнала "–Такт". Сигнал с выхода Т4 сбрасывает сигнал флага в нуль, после чего вся схема переходит в исходное состояние и ждет следующего нулевого сигнала "–Нажатие".

Если кратковременное размыкание при дребезге контактов клавиш длится более 2,5 мс, то можно увеличить количество триггеров в последовательной цепочке (Т3 и Т4), что приведет к увеличению задержки снятия сигнала флага на целое число тактов генератора.

Таким образом, схема полностью разработана. Отметим, что низкая тактовая частота работы схемы позволяет нам не рассчитывать задержек микросхем, то есть использовать только первый уровень представления, логическую модель. А эффекты, связанные с переходными процессами при переключении микросхем, мы устранили, обеспечив временной сдвиг на половину периода генератора между тактовыми сигналами схемы преобразователя (рис. 14.4) и схемы выработки выходных сигналов (рис. 14.5). Все резисторы, примененные в схеме, должны быть номиналом около 1 кОм.

Разработка вычислителя контрольной суммы

Различные контрольные суммы широко применяются в цифровых устройствах и системах для контроля правильности хранения или передачи массивов информации. Суть этого метода контроля проста: к хранимому или передаваемому информационному массиву присоединяется небольшой контрольный код (обычно от 1 разряда до 32 разрядов), в котором в свернутом виде содержится информация обо всем массиве. При чтении или получении этого массива еще раз вычисляется тот же самый контрольный код по тому же самому алгоритму. Если этот вновь вычисленный код равен тому коду, который был присоединен к массиву, то считается, что массив сохранен или передан без ошибок. Логика здесь следующая: контрольный код (он же контрольная сумма ) гораздо меньше контролируемого массива, поэтому вероятность искажения контрольной суммы гораздо меньше, чем вероятность искажения массива. Если же исказятся как массив, так и контрольная сумма, то вероятность того, что эти искажения не будут замечены при повторном подсчете контрольной суммы, крайне мала. Существует, правда, вероятность, что массив будет искажен в нескольких местах таким образом, что контрольная сумма от этих искажений никак не изменится, но такая вероятность также обычно мала.

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

Существует множество способов вычисления контрольной суммы, различающихся степенью сложности вычисления и надежностью выявления ошибок. Но наибольшее распространение получил в настоящее время так называемый "циклический метод контроля по избыточности" или CRC (Cyclic Redundancy Check), при котором применяется циклическая контрольная сумма.

Вычисляется циклическая контрольная сумма следующим образом. Весь массив информации рассматривается как одно N-разрядное двоичное число, где N — количество бит во всех байтах массива. Для вычисления контрольной суммы это N-разрядное число делится на некоторое постоянное число ( полином ), выбранное специальным образом (но делится не просто, а по модулю 2). Частное от этого деления отбрасывается, а остаток как раз и используется в качестве контрольной суммы.

Мы не будем углубляться в математическое обоснование этого метода. Интересующиеся читатели могут обратиться к специальной литературе. Здесь же мы отметим только, что данный метод выявляет одиночные ошибки в массиве с вероятностью 100%, а любое другое количество ошибок с вероятностью, примерно равной 1–2-n, где n — количество разрядов контрольной суммы (это верно только при условии, что N гораздо больше n, что, впрочем, почти всегда выполняется). Например, при n = 8 данная вероятность составит 0,996, для n = 16 она будет равна 0,999985, а для n = 32 она будет 0,9999999997672. Иначе говоря, почти все ошибки будут выявляться.

А теперь кратко поясним, что такое деление по модулю 2. Пусть массив (последовательность бит) имеет следующий вид: 101111001110 (для простоты берем небольшую разрядность). Число, на которое делим (называемое обычно образующим полиномом ) возьмем 10011. Как оно выбирается? Оно должно делиться по модулю 2 без остатка только на единицу и само на себя (то есть это должно быть простое число в смысле деления по модулю 2). Разрядность полинома берется на единицу большая, чем требуемая разрядность контрольной суммы (остатка от деления). Так, чтобы получить 8-разрядный остаток (8-разрядную контрольную сумму), надо брать 9-разрядный полином. В нашем случае полином 5-разрядный, следовательно, остаток будет 4-разрядный. Для получения 8-разрядного остатка можно использовать, например, полином 1 0001 1101 или 11D в 16-ричном коде.

Деление по модулю 2 производится точно так же, как и привычное для нас деление "в столбик" (рис. 14.6), но вместо вычитания в данном случае используется поразрядное сложение по модулю 2, то есть каждый результирующий бит представляет собой функцию Исключающее ИЛИ от соответствующих битов слагаемых. Частное от деления нас не интересует, а остаток, равный в нашем примере 1000, и будет циклической контрольной суммой.

Как практически реализовать вычисление этого остатка (контрольной суммы)? Можно сделать это по приведенному здесь принципу деления в столбик (аппаратно или программно). Но в любом случае это довольно громоздко и медленно. Ускорить процесс вычисления можно, воспользовавшись табличным методом. Для этого составляется таблица чисел размером 2nхn, где n — разрядность контрольной суммы. Принцип вычисления чисел в таблице очень прост (табл. 14.1).

Числа представляют собой остаток от деления по модулю 2 числа с n конечными нулями (в нашем примере n = 8) и с n начальными разрядами, равными номеру числа (его адресу) в таблице. Деление производится на выбранный полином (в нашем случае — 9-разрядный). Таблица вычисляется один раз и хранится на диске или в ПЗУ.

Алгоритм вычисления контрольной суммы с помощью этой таблицы следующий (рассматриваем случай n = 8). Берем первый байт нашего информационного массива. Рассматриваем его как адрес в таблице (номер числа). Берем из таблицы число с полученным номером — получаем остаток О1. Берем второй байт массива и складываем его по модулю 2 с остатком О1. Полученное число используем как адрес в таблице. По этому адресу выбираем из таблицы остаток О2. Берем третий байт массива, складываем его по модулю 2 с остатком О2. Используя это число как адрес в таблице, выбираем из нее остаток О3 и так продолжаем до последнего байта массива. Естественно, это будет гораздо быстрее, чем вычисление "в столбик".

Реализация этого алгоритма с помощью цифровых схем требует только ПЗУ с организацией 2ⁿхn (256х8 при 8-разрядной контрольной сумме), n-разрядного регистра и n элементов Исключающее ИЛИ (рис. 14.7). В ПЗУ заносится таблица промежуточных остатков (табл. 14.1), на вход схемы подаются один за другим байты массива, сопровождаемые стробом. Адресом ПЗУ служит сумма по модулю 2 входных данных и содержимого выходного регистра, в который по сигналу строба записывается выходной код ПЗУ. Перед началом вычисления состояние регистра обнуляется. После окончания всего массива в регистре образуется циклическая контрольная сумма.

Недостаток данной схемы параллельного вычислителя очевиден: в случае большого числа разрядов контрольной суммы требуется очень большой объем ПЗУ (64Кх16 для 16-разрядной суммы и 4Гх32 для 32-разрядной суммы). Поэтому она применяется сравнительно редко. Зато параллельный вычислитель обладает высоким быстродействием (байты могут поступать с периодом, равным сумме задержки выходного регистра, времени выборки адреса ПЗУ и задержки элемента Исключающее ИЛИ).

Для многоразрядной контрольной суммы чаще применяется другой подход — вычисление в последовательном коде, при котором массив данных поступает на вычислитель последовательно, бит за битом. Последовательный вычислитель контрольной суммы представляет собой сдвиговый регистр с обратными связями от некоторых разрядов через сумматоры по модулю 2 (то есть элементы Исключающее ИЛИ). Полное количество разрядов регистра сдвига должно быть равно разрядности вычисляемой контрольной суммы (или, что то же самое, быть на единицу меньше разрядности используемого полинома). Место включения обратных связей однозначно определяется выбранным полиномом. Это очень похоже на генератор квазислучайной последовательности.

Количество точек включения обратной связи определяется количеством единиц в полиноме (единица в младшем разряде не учитывается), а номера разрядов сдвигового регистра, с которых берутся сигналы обратной связи, определяются номерами единичных разрядов в коде полинома. В отличие от генератора квазислучайного сигнала, в данном случае необходимо смешать по функции Исключающее ИЛИ не только сигналы обратной связи, но и входной сигнал данных в последовательном коде.

На рис. 14.8 приведен пример последовательного вычислителя 16-разрядной циклической контрольной суммы при выбранном полиноме 1 0001 0000 0010 0001 или 11021 в 16-ричном коде (ре­ко­мен­да­ция МККТТ V.41). Так как в коде полинома три единицы (без младшего разряда), необходимо взять три точки включения обратной связи. При этом номера разрядов сдвигового регистра, к которым подключаются обратные связи, определяются положением единичных битов в полиноме. Перед началом работы сдвиговый регистр необходимо сбросить в нуль (сигнал "–Сброс"). Биты массива должны сопровождаться сигналом строба. После окончания массива в регистре будет циклическая контрольная сумма.

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

Период поступления битов массива на последовательный вычислитель не должен быть меньше суммы задержки регистра сдвига и элементов Исключающее ИЛИ. В итоге предельная скорость вычисления циклической контрольной суммы оказывается значительно меньшей, чем в случае параллельного вычислителя. Это также недостаток данного метода вычисления.