Разработка вычислителя контрольной суммы
Различные контрольные суммы широко применяются в цифровых устройствах и системах для контроля правильности хранения или передачи массивов информации. Суть этого метода контроля проста: к хранимому или передаваемому информационному массиву присоединяется небольшой контрольный код (обычно от 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, и будет циклической контрольной суммой.
Рис. 14.6. Вычисление циклической контрольной суммы
|
Разработка клавиатуры
Различные клавиатуры с большим количеством клавиш (кнопок) широко используются в цифровых системах: в компьютерах, контроллерах, измерительных приборах, в бытовой технике. Основная задача любой клавиатуры довольно проста: она должна при любом нажатии на клавишу выдавать код номера этой клавиши и сигнал флага нажатия клавиши (строб этого кода). Получив этот сигнал флага, внешнее устройство читает код нажатой клавиши и предпринимает требуемые действия.
Главная задача при проектировании клавиатуры состоит в минимизации аппаратных затрат и в обеспечении надежного срабатывания в любой ситуации. Существует масса схемотехнических решений этой задачи — от примитивных до сложнейших. Клавиатуры могут быть механическими, квазисенсорными или сенсорными, клавиатуры могут иметь жесткую логику работы или быть интеллектуальными, даже допускать перепрограммирование. Мы будем в качестве примера рассматривать самую простую механическую клавиатуру с жесткой логикой работы.
Количество клавиш полноразмерной клавиатуры компьютера превышает сотню, поэтому мы будем проектировать клавиатуру на максимальное количество клавиш, равное 128. Естественно, клавиатура должна иметь защиту от дребезга механических контактов и должна корректно обрабатывать ситуацию одновременного нажатия нескольких клавиш. Примем, например, что при одновременном нажатии нескольких клавиш клавиатура должна выдавать код только одной из них. Примем также, что максимально возможный темп нажатия клавиш на клавиатуре не должен превышать 20 нажатий в секунду (это довольно много). Таким образом, основные требования к проектируемому устройству сформулированы. Начнем разработку.
Очень часто удобным и эффективным приемом является начало разработки устройства "с конца". То есть проектирование начинается исходя из требуемого результата, из тех сигналов, которые устройство должно выдавать вовне и принимать извне. И только в конце проектирования разрабатывается та часть устройства, которая выполняет требуемую функцию. Такой подход гарантирует, что разработанное устройство не будет чрезмерно избыточным, не будет делать ничего лишнего, а также то, что оно корректно будет взаимодействовать с другими устройствами и системами. Этот принцип проектирования не универсален, порой выдержать его в течение всего процесса разработки трудно, но попробовать его применить к любому устройству никогда не помешает.
В нашем случае необходимо сначала определиться, что должна выдавать вовне клавиатура. Обычно это задается техническим заданием, но мы примем, что наша клавиатура должна выдавать 7-разрядный двоичный номер нажатой клавиши (так как 27 = 128) и сопровождать его положительным сигналом флага нажатия. Сигнал флага и код клавиши должны сохраняться до тех пор, пока нажата клавиша. За это время (несколько миллисекунд) внешнее устройство должно успеть проанализировать сигнал флага и прочитать выходной код клавиатуры. Обычно данное требование не слишком жесткое.
Альтернативное решение — сохранение кода нажатой клавиши и сигнала флага до момента чтения выходного кода внешним устройством — конечно же, снижает требование к быстродействию читающего внешнего устройства, однако оно может привести к тому, что некоторые нажатия клавиш останутся без реакции, не будут обработаны.
Также необходимо определиться, как клавиатура будет вести себя при одновременном нажатии нескольких клавиш. Наиболее сложные, интеллектуальные клавиатуры выдают последовательно коды всех нажатых клавиш, запоминая их в буферной памяти. Но мы примем, что клавиатура должна выдавать только код одной из одновременно нажатых клавиш (первой по установленному порядку). Нажатия всех остальных клавиш одновременно с данной просто игнорируются.
При проектировании механической клавиатуры важно решить, как будет обрабатываться неизбежно присутствующий дребезг механических контактов клавиш. Его можно обрабатывать как внутри клавиатуры, так и вне ее (то есть перенести эту функцию на внешнее устройство). Оба эти подхода имеют свои преимущества. Но наша клавиатура будет обрабатывать дребезг контактов самостоятельно. Принцип обработки выбираем очень простой: первое зафиксированное замыкание контактов клавиши считается началом нажатия, а конец нажатия определяется тогда, когда контакты будут разомкнуты в течение заданного интервала времени.
В результате временная диаграмма работы разрабатываемой клавиатуры может быть упрощенно представлена в виде рис. 14.1. Здесь сигнал флага начинается при фиксации единичного сигнала с клавиши (это может быть как во время дребезга, так и после его окончания). После выставления флага фиксируется выходной код клавиши. После отпускания клавиши (нулевой сигнал), через время задержки tзад снимается сигнал флага. Время задержки должно быть заведомо больше времени дребезга
...
Читать дальше »
|
В лекции подробно рассматриваются примеры разработки простых цифровых устройств — клавиатуры и вычислителя контрольной суммы, начиная от анализа функций устройств и выделения основных узлов до проектирования принципиальных схем узлов и устройства в целом.
Содержание Разработка клавиатуры Разработка вычислителя контрольной суммы В предыдущих лекциях были рассмотрены базовые элементы цифровой схемотехники и простейшие приемы проектирования узлов на их основе. Но для разработки сложных устройств и систем всех этих знаний порой оказывается недостаточно.
Чтобы создать сложное устройство, необходимо еще владеть приемами системотехники, то есть уметь на основании анализа функций, которые должно выполнять устройство в целом, спроектировать его структуру, сформулировать принципы взаимодействия узлов, четко определить все задачи, которые должен решать каждый из узлов, выработать требования к отдельным узлам. Возможно, в результате всех этих шагов будет изменена сама первоначальная задача, будут переформулированы требования к создаваемому устройству, к его месту в системе, к принципам его взаимодействия с другими устройствами. И только потом, после всей этой предварительной работы уже можно переходить к разработке узлов, собственно к схемотехнике.
Приемы системотехники сформулировать, формализовать, описать, даже перечислить гораздо сложнее, чем приемы схемотехники. Да и пользы от такой формализации зачастую немного. Проектирование сложного, надежно работающего цифрового устройства с минимальными аппаратными затратами сродни искусству и требует от разработчика определенных способностей, даже таланта. Научить этому практически невозможно. Более того, попытка научить системотехнике может даже принести вред, так как ограничит творческие способности разработчика несколькими жесткими стандартными алгоритмами.
Однако можно показать несколько простейших примеров разработки, продемонстрировать последовательность шагов, которые необходимы при проектировании, которые могут встретиться в процессе создания устройств некоторых распространенных типов. Исходя из этих примеров, разработчик может в дальнейшем попробовать по аналогии создать что-то свое, более или менее совершенное, но обязательно работоспособное.
Поэтому в данной лекции как раз и будут подробно рассмотрены несколько простых примеров проектирования сравнительно сложных устройств на всех этапах: от анализа решаемой задачи до создания полной принципиальной схемы. Примеры эти, конечно, не отражают и малой доли всех реально встречающихся задач, но относятся к различным классам цифровых устройств.
| |
