Как сделать шифратор на с
Добавил пользователь Алексей Ф. Обновлено: 18.09.2024
Метод 1 Коды
Стандартные коды
Книга кода
Полицейское кодирование
Метод 2 Шифры
Шифрование, основанное на дате
Шифрование при помощи числа
Графический шифр
Перестановка Цезаря
Метод 3 Секретные языки
Путаный язык
Звуковой код
Тарабарский язык
Советы
Предупреждения
- Если вы пишете код неаккуратно, то это сделает процесс декодирования более сложным для вашего партнера, при условии что вы не используете вариации кодов или шифров, созданные специально, чтобы запутать дешифровальщика (за исключением вашего партнера, конечно).
- Путаный язык лучше использовать для коротких слов. С длинными словами он не настолько эффективен, потому что дополнительные буквы гораздо более заметны. То же самое при использовании его в речи.
Что вам понадобится
- Партитура для кода
- Карандаш
- Бумага
- Любая дата
Шифр — какая-либо система преобразования текста с секретом (ключом) для обеспечения секретности передаваемой информации. Прочитав определение из википедии , конечно можно понять что такое шифр , но все же не до конца. Что-бы понять что же делает шифры таким особенным , популярным , а чаще всего и жизненно-важным , в первую очередь надо что-нибудь зашифровать.
В цикле статей под название “Создание своего метода шифрования”, эта статья будет вводной. Здесь мы рассмотрим отличие шифров от кодов и выберем 2 шифра, которые в дальнейшем мы будем использовать для создания своего шифра.
Отличие шифров от кодов
Если не вдаваться в глубокие подробности, то ответ очень прост. Представьте себе обычную телефонную книгу. Представили? Телефонная книга и есть своего рода кодовая книга. Если вы будете записывать фамилии и имена ваших друзей на обычный листок то получится текст , а если вместо их ФИО использовать номера их телефонов то получится уже закодированное послание. Такое послание сможет понять только тот человек, который знает, что при составлении этого текста вы использовали телефонную книгу. И раскодировать этот набор цифр он сможет только при помощи такой же телефонной книги. Очевидным минусом кодов , является их “стабильность”. При попадании кодовой книги к тому , от кого вы свое послание прятали , ваш код будет больше не способен обеспечить скрытность переписки.
Выбор шифров для скрещивания
Ну что ж вот и основная часть статьи. Не буду откладывать в долгий ящик и расскажу какие шифры мы будем использовать. Шифр Вижинера и Квадрат Полибия.
Квадрат Полибия
Чуть выше я писал, что код намного менее универсален и порой менее устойчив к взлому. Но квадрат Полибия это код простой замены, причем очень древний код. Так почему же , если он такой простой использовать мы будем его ? Как раз потому что он такой простой , уж простите за тавтологию. Работу с данным шифром разделим на несколько стадий :
- Выбор языка алфавита для таблицы
- Определение размерности таблицы
- Формирование таблицы
- Шифрования
Алфавит мы возьмем русский , а таблицу самую часто используемую. Принцип шифрования понятен даже ребенку :
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | А | Б | В | Г | Д | Е |
| 2 | Ё | Ж | З | И | Й | К |
| 3 | Л | М | Н | О | П | Р |
| 4 | С | Т | У | Ф | Х | Ц |
| 5 | Ч | Ш | Щ | Ъ | Ы | Ь |
| 6 | Э | Ю | Я | — | — | — |
Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от неё в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца.
| Буква текста: | а | р | б | у | з |
| Буква шифротекста : | ё | ш | ж | з | н |
Шифр Вижинера
Данный шифр тоже далеко не новый , но взломать его (официально )не могли целых 200 лет. Шифр Вижинера это поли алфавитный шифр , да к тому же еще с ключевым словом.
Попробуем зашифровать слово PENSIL. Ключевым словом будет слово MEN.
P E NS I L MENMEN
Ключевое слово будем писать циклично до конца текста. Потом Используя таблицу выше , будем искать и находить символы на перекрестиях буквы из текста и буквы из кодового слова. Если все правильно зашифровать то должно получиться слово — BIAETY.
Объединения шифра Вижинера и квадрата Полибия
| 1 | 2 | 3 | 4 | 5 | |
| 1 | А | Б | В | Г | Д |
| 2 | Е | Ж | З | И | К |
| 3 | Л | М | Н | О | П |
| 4 | Р | С | Т | У | Ф |
| 5 | Х | Ц | Ч | Ш | Щ |
| 6 | Ы | Э | Ю | Я |
| л | и | м | о | н | |
| м | А | Б | В | Г | Д |
| у | Е | Ж | З | И | К |
| з | Л | М | Н | О | П |
| ы | Р | С | Т | У | Ф |
| к | Х | Ц | Ч | Ш | Щ |
| а | Ы | Э | Ю | Я |
Вот так просто мы и объединили два шифра. Полученный текс расшифровать гораздо сложнее чем обычный шифр Полибия. Правда в стойкости примененный шифр проигрывает шифру Вижинера , так как является одно алфавитным. Однако новый принцип существенно легче и проще для повседневного использования, или шифрования не очень важной информации.
Прежде всего, разберемся в терминологии.
Ключ — это компонент, на основе которого можно произвести шифрование или дешифрование.
Теперь, когда мы говорим на более-менее одном языке, разберем простые шифры.
Шифр Атбаша
Самый-самый простой шифр. Его суть – переворот алфавита с ног на голову.
Например, есть у нас алфавит, который полностью соответствует обычной латинице.
И теперь пишем нужное сообшение на исходном алфавите и алфавите шифра
Шифр Цезаря
Тут добавляется еще один параметр — примитивный ключ в виде числа от 1 до 25 (для латиницы). На практике, ключ будет от 4 до 10.
Опять же, для наглядности, возьмем латиницу
И теперь сместим вправо или влево каждую букву на ключевое число значений.
Например, ключ у нас будет 4 и смещение вправо.
Исходный алфавит: a b c d e f g h i j k l m n o p q r s t u v w x y z
Зашифрованный: w x y z a b c d e f g h i j k l m n o p q r s t u v
Шифруем его и получаем следующий несвязный текст:
Шифр Вернама (XOR-шифр)
Простейший шифр на основе бинарной логики, который обладает абсолютной криптографической стойкостью. Без знания ключа, расшифровать его невозможно (доказано Клодом Шенноном).
Исходный алфавит — все та же латиница.
XOR принимает сигналы (0 или 1 каждый), проводит над ними логическую операцию и выдает один сигнал, исходя из входных значений.
Если все сигналы равны между собой (0-0 или 1-1 или 0-0-0 и т.д.), то на выходе получаем 0.
Если сигналы не равны (0-1 или 1-0 или 1-0-0 и т.д.), то на выходе получаем 1.
Переведем их в бинарный код и выполним XOR:
В данном конкретном примере на месте результирующих символов мы увидим только пустое место, ведь все символы попали в первые 32 служебных символа. Однако, если перевести полученный результат в числа, то получим следующую картину:
С виду — совершенно несвязный набор чисел, но мы-то знаем.
Шифр кодового слова
Принцип шифрования примерно такой же, как у шифра цезаря. Только в этом случае мы сдвигаем алфавит не на определенное число позиций, а на кодовое слово.
Например, возьмем для разнообразия, кириллический алфавит.
Теперь вписываем данное слово в начале алфавита, а остальные символы оставляем без изменений.
Получим в итоге следующий нечитаемый бред:
Шифр Плейфера
Классический шифр Плейфера предполагает в основе матрицу 5х5, заполненную символами латинского алфавита (i и j пишутся в одну клетку), кодовое слово и дальнейшую манипуляцию над ними.
Сначала поступаем как с предыдущим шифром, т.е. уберем повторы и запишем слово в начале алфавита.
Разобьем его на биграммы, т.е. на пары символов, не учитывая пробелы.
Шифрование выполняется по нескольким несложным правилам:
1) Если символы биграммы находятся в матрице на одной строке — смещаем их вправо на одну позицию. Если символ был крайним в ряду — он становится первым.
Например, EH становится LE.
2) Если символы биграммы находятся в одном столбце, то они смещаются на одну позицию вниз. Если символ находился в самом низу столбца, то он принимает значение самого верхнего.
Например, если бы у нас была биграмма LX, то она стала бы DL.
3) Если символы не находятся ни на одной строке, ни на одном столбце, то строим прямоугольник, где наши символы — края диагонали. И меняем углы местами.
Например, биграмма RA.
Поздравляю. После прочтения этой статьи вы хотя бы примерно понимаете, что такое шифрование и знаете как использовать некоторые примитивные шифры и можете приступать к изучению несколько более сложных образцов шифров, о которых мы поговорим позднее.
Одними из очень важных элементов цифровой техники, а особенно в компьютерах и системах управления являются шифраторы и дешифраторы.
Когда мы слышим слово шифратор или дешифратор, то в голову приходят фразы из шпионских фильмов. Что-то вроде: расшифруйте депешу и зашифруйте ответ.
В этом нет ничего неправильного, так как в шифровальных машинах наших и зарубежных резидентур используются шифраторы и дешифраторы.
Шифраторы.
Таким образом, шифратор (кодер), это электронное устройство, в данном случае микросхема, которая преобразует код одной системы счисления в код другой системы. Наибольшее распространение в электронике получили шифраторы, преобразующие позиционный десятичный код, в параллельный двоичный. Вот так шифратор может обозначаться на принципиальной схеме.
К примеру, представим, что мы держим в руках обыкновенный калькулятор, которым сейчас пользуется любой школьник.
Поскольку все действия в калькуляторе выполняются с двоичными числами (вспомним основы цифровой электроники), то после клавиатуры стоит шифратор, который преобразует вводимые числа в двоичную форму.
Все кнопки калькулятора соединяются с общим проводом и, нажав, к примеру, кнопку 5 на входе шифратора, мы тут же получим двоичную форму данного числа на его выходе.
Конечно же, шифратор калькулятора имеет большее число входов, так как помимо цифр в него нужно ввести ещё какие-то символы арифметических действий, поэтому с выходов шифратора снимаются не только числа в двоичной форме, но и команды.
Если рассмотреть внутреннюю структуру шифратора, то несложно убедиться, что он выполнен на простейших базовых логических элементах.
Во всех устройствах управления, которые работают на двоичной логике, но для удобства оператора имеют десятичную клавиатуру, используются шифраторы.
Дешифраторы.
Дешифраторы относятся к той же группе, только работают с точностью до наоборот. Они преобразуют параллельный двоичный код в позиционный десятичный. Условное графическое обозначение на схеме может быть таким.
Если говорить о дешифраторах более полно, то стоит сказать, что они могут преобразовывать двоичный код в разные системы счисления (десятичную, шестнадцатиричную и пр.). Всё зависит от конкретной цели и назначения микросхемы.
Простейший пример. Вы не раз видели цифровой семисегментный индикатор, например, светодиодный. На нём отображаются десятичные цифры и числа к которым мы привыкли с детства (1, 2, 3, 4. ). Но, как известно, цифровая электроника работает с двоичными числами, которые представляют комбинацию 0 и 1. Что же преобразовало двоичный код в десятичный и подало результат на цифровой семисегментный индикатор? Наверное, вы уже догадались, что это сделал дешифратор.
Для справки. Микросхема К176ИД2 разрабатывалась для управления 7-ми сегментным светодиодным индикатором. Эта микросхема способна преобразовать двоичный код от 0000 до 1001, что соответствует десятичным цифрам от 0 до 9 (одна декада). Остальные, более старшие комбинации просто не отображаются. Выводы C, S, K являются вспомогательными.
У микросхемы К176ИД2 есть четыре входа (1, 2, 4, 8). Их ещё иногда обозначают D0 – D3. На эти входы подаётся параллельный двоичный код (например, 0001). В данном случае, двоичный код имеет 4 разряда. Микросхема преобразует код так, что на выходах (a – g) появляются сигналы, которые и формируют на семисегментном индикаторе десятичные цифры и числа, к которым мы привыкли. Так как дешифратор К176ИД2 способен отобразить десятичные цифры в интервале от 0 до 9, то на индикаторе мы увидим только их.
Ко входам дешифратора К176ИД2 подключены 4 тумблера (S1 - S4), с помощью которых на дешифратор можно подать параллельный двоичный код. Например, при замыкании тумблера S1 на 5 вывод микросхемы подаётся логическая единица. Если же разомкнуть контакты тумблера S1 – это будет соответствовать логическому нулю. С помощью тумблеров мы сможем вручную устанавливать на входах микросхемы логическую 1 или 0. Думаю, с этим всё понятно.
На схеме показано, как на входы дешифратора DD1 подан код 0101. На светодиодном индикаторе отобразится цифра 5. Если замкнуть только тумблер S4, то на индикаторе отобразится цифра 8. Чтобы записать число от 0 до 9 в двоичном коде достаточно четырёх разрядов: a3* 8 + a2* 4 + a1* 2 + a0* 1, где a0 – a3, - это цифры из системы счисления (0 или 1).
Представим число 0101 в десятичном виде 0101 = 0*8 + 1*4 + 0*2 + 1*1 = 4 + 1 = 5. Теперь взглянем на схему и увидим, что вес разряда соответствует цифре, на которую умножается 0 или 1 в формуле.
Дешифратор на базе технологии ТТЛ – К155ИД1 использовался в своё время для управления газоразрядным цифровым индикатором типа ИН8, ИН12, которые были очень востребованы в 70-е годы, так как светодиодные низковольтные индикаторы ещё были очень большой редкостью.
Всё изменилось в 80-е годы. Можно было свободно приобрести семисегментные светодиодные матрицы (индикаторы) и среди радиолюбителей прокатился бум сборки электронных часов. Самодельные электронные часы не собрал для дома только ленивый.
Двоичный шифратор выполняет логическую функцию преобразования унарно n-ичного однозначного кода в двоичный. При подаче сигнала на один из n входов (обязательно на один, не более) на выходе появляется двоичный код номера активного входа.
Если количество входов настолько велико, что в шифраторе используются все возможные комбинации сигналов на выходе, то такой шифратор называется полным, если не все, то неполным. Число входов и выходов в полном шифраторе связано соотношением:
где n— число входов, m— число выходных двоичных разрядов.
Троичный шифратор выполняет логическую функцию преобразования унарно n-ичного однозначного (одноединичного или однонулевого) кода в троичный. При подаче сигнала ("1" в одноединичном коде или "0" в однонулевом коде) на один из n входов на выходе появляется троичный код номера активного входа.
Число входов и выходов в полном троичном шифраторе связано соотношением:
где n- число входов, m- число выходных троичных разрядов.
Число входов и выходов в полном k-ичном шифраторе связано соотношением:
где n- число входов, m- число выходных k-ичных разрядов, k- основание системы счисления.
Приоритетный шифратор отличается от шифратора наличием дополнительной логической схемы выделения активного уровня старшего входа для обеспечения условия работоспособности шифратора (только один уровень на входе активный). Уровни сигналов на остальных входах схемой игнорируются.
При построении шифратора для получения на выходе натурального двоичного кода учитывают, что единицу в младшем разряде такого кода имеют нечетные десятичные цифры 1, 3, 5, 7, . , т. е. на выходе младшего разряда должна быть 1, если она есть на входе № 1 или на входе № 3 и т. д. Поэтому входы под указанными номерами через элемент ИЛИ соединяются с выходом младшего разряда. Единицу во втором разряде двоичного кода имеют десятичные цифры 2, 3, 6, 7, . . .; входы с этими номерами через элемент ИЛИ должны подключаться к выходу шифратора, на котором устанавливается второй разряд кода. Аналогично, входы 4, 5, 6, 7. через элемент ИЛИ должны быть соединены с выходом, на котором устанавливается третий разряд, так как их коды имеют в этом разряде единицу, и т. д.
Шифратор может быть организован не только для представления (кодирования) десятичного числа двоичным кодом, но и для выдачи определенного кода (его значение заранее выбирается), например, при нажатии клавиши с соответствующим символом. При появлении этого кода система оповещается о том, что нажата определенная клавиша клавиатуры.
Шифраторы применяются в устройствах, преобразующих один вид кода в другой. При этом вначале дешифрируется комбинация исходного кода, в результате чего на соответствующем выходе дешифратора появляется логическая 1. Это отображение входного кода, значение которого определено номером возбужденного выхода дешифратора, подается на шифратор, организованный с таким расчетом, чтобы каждый входной код вызывал появление заданного выходного кода.
Таблица истинности для шифратора из 12 в 4
Электрическая функциональная схема шифратора
Электрическая принципиальная схема шифратора
DD1-DD2: К155ЛД1 (сумматор на 8 входов)
DD3: К155ЛЕ3 (4ИЛИ-НЕ) DD4: К155ЛН1 (Инверторы)
Дешифраторы
Дешифратор (декодер) — комбинационное устройство, преобразующее n-разрядный двоичный, троичный или k-ичный код в -ичный одноединичный код, где k - основание системы счисления. Логический сигнал появляется на том выходе, порядковый номер которого соответствует двоичному, троичному или k-ичному коду. [6]
Дешифраторы являются устройствами, выполняющими двоичные, троичные или k-ичные логические функции (операции).
Это комбинационные схемы с несколькими входами и выходами, преобразующие код, подаваемый на входы в сигнал на одном из выходов. На выходе дешифратора появляется логическая единица, на остальных — логические нули, когда на входных шинах устанавливается двоичный код определённого числа или символа, то есть дешифратор расшифровывает число в двоичном, троичном или k-ичном коде, представляя его логической единицей на определённом выходе. Число входов дешифратора равно количеству разрядов поступающих двоичных, троичных или k-ичных чисел. Число выходов равно полному количеству различных двоичных, троичных или k-ичных чисел этой разрядности.
Для n-разрядов на входе, на выходе 2 n , 3 n или k n . Чтобы вычислить, является ли поступившее на вход двоичное, троичное или k-ичное число известным ожидаемым, инвертируются пути в определённых разрядах этого числа. Затем выполняется конъюнкция всех разрядов преобразованного таким образом числа. Если результатом конъюнкции является логическая единица, значит на вход поступило известное ожидаемое число.
Из логических элементов являющихся дешифраторами можно строить дешифраторы на большое число входов. Каскадное подключение таких схем позволит наращивать число дифференцируемых переменных.
Двоичный дешифратор работает по следующему принципу: пусть дешифратор имеет N входов, на них подано двоичное слово xN − 1xN − 2. x0, тогда на выходе будем иметь такой код, разрядности меньшей или равной 2 N , что разряд, номер которого равен входному слову, принимает значение единицы, все остальные разряды равны нулю. Очевидно, что максимально возможная разрядность выходного слова равна 2 N . Такой дешифратор называется полным. Если часть входных наборов не используется, то число выходов меньше 2 N , и дешифратор является неполным.
Часто дешифраторы дополняются входом разрешения работы E. Если на этот вход поступает единица, то дешифратор функционирует, в ином случае на выходе дешифратора вырабатывается логический ноль вне зависимости от входных сигналов.
Существуют дешифраторы с инверсными выходами, у такого дешифратора выбранный разряд показан нулём.
Основное назначение дешифратора состоит в том, чтобы выбрать (адресовать, инициализировать) один объект из множества находящихся в устройстве. Каждому объекту присваивают определенный адрес (номер). Когда на входы дешифратора поступает двоичный код адреса, соответствующий элемент активизируется за счет появления логического 0 на связанном с ним выходе дешифратора, а остальные элементы остаются заблокированными.
Можно предусмотреть, чтобы с одного из выходов дешифратора на определенный блок поступал управляющий сигнал, когда на входах дешифратора появляется определенный код, соответствующий, например, превышению какого-либо параметра (температуры, напряжения и т.д.), который должен быть приведен к нормальному уровню указанным блоком.
Когда число адресуемых устройств невелико, многие выходы дешифратора остаются незадействованными. При этом может оказаться целесообразным (в частности, по экономическим соображениям) использовать не микросхему дешифратора, а реализовать ее фрагмент логическими элементами.
Электрическая функциональная схема дешифратора
Электрическая принципиальная схема дешифратора
DD2-DD7: К155ЛИ6 (4И)
Карты Карно
Карта Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба. [10]
В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.
Карты Карно являются альтернативным способом представления таблицы истинности в виде двухмерной сетки.
Рис.2.1. Пример карты Карно
Правила минимизации логических выражений с помощью карт Карно просты: [2]
1. Постройте карту Карно, исходя либо из логического выражения, либо из таблицы истинности.
2. Образуйте новые группы, состоящие из единиц. Образовывать группы можно только по вертикали и горизонтали (не по диагонали!), и стремитесь к тому, чтобы этих групп было как можно больше. Группы могут частично перекрываться (совпадать) и распространяться вверх и в стороны.
3. Теперь считайте с карты новые группы и запишите их в виде суммы произведений.
Рассмотрим этот способ на примере схемы мажоритарного выбора, описанной ранее. На Рис.2.4а представлена ее карта Карно. С помощью правил, приведенных выше, образуем новые группы единиц (Рис.2.46) и упростим выражение:
Минимизированная схема мажоритарного выбора представлена на Рис. Рис.2.4в. Минимизация комбинационных схем с помощью карт Карно — это самый простой способ минимизации, поскольку наибольшие возможные группы единиц легко заметны.
Рис. 2.4. Упрощение схемы мажоритарного выбора:
а — исходная карта Карно;
б — создание новых групп;
в — упрощенная схема
Семисегментный индикатор
Семисегме́нтный индика́тор — устройство отображения цифровой информации. Это — наиболее простая реализация индикатора, который может отображать арабские цифры. Для отображения букв используются более сложные многосегментные и матричные индикаторы. [1]
Семисегментный индикатор, как говорит его название, состоит из семи элементов индикации (сегментов), включающихся и выключающихся по отдельности. Включая их в разных комбинациях, из них можно составить упрощённые изображения арабских цифр. Часто семисегментные индикаторы делают в курсивном начертании, что повышает читаемость.
Цифры, 6, 7 и 9 имеют по два разных представления на семисегментном индикаторе.
Сегменты обозначаются буквами от A до G; восьмой сегмент — десятичная запятая, предназначенная для отображения дробных чисел.
Изредка на семисегментном индикаторе отображают буквы.
Светодиодные индикаторы имеют предельно простую форму, так как в них применяются светодиоды, отлитые в форме сегментов, и чем меньше разных типов светодиодов, тем дешевле устройство. В жидкокристаллических, газорязрядных, вакуумно-люминесцентных (катодно-люминесцентных) и других индикаторах дизайнеры находят место для вариации формы сегментов.
Большинство одноразрядных семисегментных индикаторов устроены на светодиодах, хотя существуют и альтернативы — лампы тлеющего разряда, электровакуумные индикаторы (катодолюминесцентные, накаливаемые), лампы накаливания, жидкие кристаллы и т. д. На больших табло наподобие цен на бензин всё ещё применяются механические индикаторы, переключающиеся с помощью электромагнитов.
Многоразрядные индикаторы часто устроены по матричному принципу. Выводы всех одноимённых сегментов всех разрядов соединены вместе. Чтобы выводить информацию на такой индикатор, управляющая микросхема должна циклически подавать ток на общие выводы всех разрядов, в то время как на выводы сегментов ток подаётся в зависимости от того, зажжён ли данный сегмент в данном разряде. Таким образом, чтобы получить десятиразрядный экран микрокалькулятора, нужны всего восемнадцать выводов (8 анодов и 10 катодов) — а не 81. Сходным образом сканируется клавиатура калькулятора.
Существуют специальные микросхемы семисегментных дешифраторов, переводящие четырёхбитный код в его семисегментное представление. К примеру, отечественные КР514ИД1 для индикаторов с общим катодом или КР514ИД2 с общим анодом. Иногда дешифраторы встраивают прямо в индикатор.
Часто на ценниках применяются закрашиваемые фломастером сегменты. Также встречаются трафареты в виде семисегментных индикаторов для изображения цен или телефонных номеров.
Отображение букв.
Кроме десяти цифр, семисегментные индикаторы способны отображать буквы. Но лишь немногие из букв имеют интуитивно понятное семисегментное представление. [4]
В латинице: заглавные A, B, C, E, F, G, H, I, J, L, N, O, P, S, U, Y, Z, строчные a, b, c, d, e, g, h, i, n, ñ, o, q, r, t, u.
В кириллице: А, Б, В, Г, г, Е, и, Н, О, о, П, п, Р, С, с, У, Ч, Ы(два разряда), Ь, Э/З.
Карта Карно для сегмента b:
 |  |  |  | |
 | 0 | 0 | 0 | 0 |
 | 0 | 1 | 0 | 1 |
 | 0 | 0 | 0 | 0 |
 | 0 | 0 | 0 | 0 |
Электрическая принципиальная схема сегмента b
Конечный автомат
Автомат–абстрактная модель устройства, функционирующего в дискретном времени, которая перерабатывает конечную последовательность входных сигналов (стимулов) и превращает их в конечную последовательность выходных сигналов (реакций).
В процессе работы конечного автомата происходит последовательная смена конечного число его внутренних состояний, причем состояние автомата в определенный момент времени однозначно определяется входным и выходным сигналами. Такие автоматы представляют собой основу всей современной вычислительной техники и всевозможных дискретных систем автоматического контроля и управления.
В комбинационных схемах выходные сигналы однозначно определяются входными сигналами и не зависят от входных сигналов в предшествующие моменты времени. Сейчас мы приступаем к изучению второго большого класса схем ЦВМ, которые содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени.
Автоматом называется дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Если множество
состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.
Понятие состояния введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходные сигналы которых зависят не только от состояния входов в данный момент времени, но и от некоторых предысторий, т.е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в данный момент времени.
Информацию, поступающую на вход автомата, а так же выходную информацию принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв данного алфавита – словами в этом алфавите.
Принцип работы шифратора заключается в том, что выходы [math]z_0[/math] , [math]z_1[/math] , [math]\ldots[/math] , [math]z_[/math] кодируют один из входов [math]s_0[/math] , [math]s_1[/math] , [math]\ldots[/math] , [math]s_[/math] в двоичной системе счисления. Очевидно, что если подать на несколько входов значение [math]1[/math] , то такая схема будет работать некорректно. В качестве примера рассмотрим шифратор [math]4[/math] -to- [math]2[/math] . Если [math]s_0 = 1[/math] , то [math]z_0 = z_1 = 0[/math] , если же [math]s_1 = 1[/math] , то [math]z_0 = 1[/math] и [math]z_1 = 0[/math] . Остальные случаи разбираются аналогичным образом.
| [math]S_0[/math] | [math]S_1[/math] | [math]S_2[/math] | [math]S_3[/math] | [math]Z_0[/math] | [math]Z_1[/math] |
|---|---|---|---|---|---|
| [math]\textbf[/math] | [math]0[/math] | [math]0[/math] | [math]0[/math] | [math]0[/math] | [math]0[/math] |
| [math]0[/math] | [math]\textbf[/math] | [math]0[/math] | [math]0[/math] | [math]0[/math] | [math]1[/math] |
| [math]0[/math] | [math]0[/math] | [math]\textbf[/math] | [math]0[/math] | [math]1[/math] | [math]0[/math] |
| [math]0[/math] | [math]0[/math] | [math]0[/math] | [math]\textbf[/math] | [math]1[/math] | [math]1[/math] |
Построить логическую схему шифратора можно следующим образом: давайте будем использовать гейт [math]OR[/math] , который имеет [math]m[/math] входов (где [math]m[/math] — какое-то натуральное число), и на выходе возвращает [math]0[/math] , если на всех его входах будет подано [math]0[/math] , в противном случае этот гейт вернёт [math]1[/math] . Давайте рядом с каждым выходом [math]z_i[/math] поставим гейт [math]OR[/math] , и будем, по необходимости, расширять этот гейт. Тогда для каждого входа рассмотрим двоичное представление номера этого входа, и если на [math]i[/math] -ом месте стоит [math]1[/math] , то соединим этот вход с гейтом [math]OR[/math] , который соединён с выходом [math]z_i[/math] . Очевидно, если подать ровно на один вход [math]1[/math] , то выходы будут кодировать это число в двоичном представлении (если подать [math]1[/math] на вход [math]s_0[/math] , то на всех выходах будет [math]0[/math] , а сам вход не будет соединён ни с каким гейтом).
Суть дешифратора заключается в том, что с помощью [math]n[/math] входов [math]s_0[/math] , [math]s_1[/math] , [math]\ldots[/math] , [math]s_[/math] можно задавать выход, на который будет подаваться [math]1[/math] . Для того, чтобы лучше понять, как работает дешифратор, рассмотрим в качестве примера дешифратор [math]2[/math] -to- [math]4[/math] (это значит, что у этого дешифратора есть два входа [math]s_0[/math] и [math]s_1[/math] и четыре выхода [math]z_0[/math] , [math]z_1[/math] , [math]z_2[/math] и [math]z_3[/math] ). Если [math]s_0 = s_1 = 0[/math] , то на выходе [math]z_0[/math] будет значение [math]1[/math] , на остальных выходах будет [math]0[/math] . Если же [math]s_0 = 1[/math] , [math]s_1 = 0[/math] , то на выходе [math]z_1[/math] будет [math]1[/math] , на остальных выходах будут [math]0[/math] . Если [math]s_0 = 0[/math] , [math]s _1 = 1[/math] , то на выходе [math]z_2[/math] будет [math]1[/math] , а на остальных входах будет [math]0[/math] . Если же [math]s_0 = s_1 = 1[/math] , то на выходе [math]z_3[/math] будет [math]1[/math] , а на других — [math]0[/math] .
| [math]S_0[/math] | [math]S_1[/math] | [math]Z_0[/math] | [math]Z_1[/math] | [math]Z_2[/math] | [math]Z_3[/math] |
|---|---|---|---|---|---|
| [math]\textbf[/math] | [math]\textbf[/math] | [math]\textbf[/math] | [math]0[/math] | [math]0[/math] | [math]0[/math] |
| [math]\textbf[/math] | [math]\textbf[/math] | [math]0[/math] | [math]\textbf[/math] | [math]0[/math] | [math]0[/math] |
| [math]\textbf[/math] | [math]\textbf[/math] | [math]0[/math] | [math]0[/math] | [math]\textbf[/math] | [math]0[/math] |
| [math]\textbf[/math] | [math]\textbf[/math] | [math]0[/math] | [math]0[/math] | [math]0[/math] | [math]\textbf[/math] |
Давайте построим логическую схему дешифратора рекурсивным способом: допустим, что мы построили схему для [math]n-1[/math] входа, теперь попробуем слить [math]n[/math] -ый выход с предыдущими [math]n-1[/math] . Для [math]n=1[/math] схема выглядит тривиальным образом: от входа [math]s_0[/math] отходят два провода, один напрямую соединён с выходом [math]z_1[/math] , другой соединён с гейтом [math]NOT[/math] , а гейт [math]NOT[/math] соединён с выходом [math]z_0[/math] . Теперь допустим, что мы можем построить схему для [math]n-1[/math] входов. Тогда [math]n[/math] -ый вход соединим с дешифратором [math]1[/math] -to- [math]2[/math] , а первые [math]n-1[/math] входы соединим с дешифратором [math](n-1)[/math] -to- [math](2^)[/math] и потом соединим каждый выход дешифратора [math](n-1)[/math] -to- [math](2^)[/math] с каждым выходом дешифратора [math]1[/math] -to- [math]2[/math] с помощью гейтов [math]AND[/math] , потом соединим соответствующие гейты с выходами [math]z_i[/math] таким образом, чтобы значение на входе [math]z_i[/math] было равно [math]1[/math] только в том случае, если число [math]i[/math] кодируется входами [math]s_0[/math] , [math]s_1[/math] , [math]\ldots[/math] , [math]s_[/math] . Очевидно, что мы таким образом перебрали всевозможные комбинации значений на входах [math]s_0[/math] , [math]s_1[/math] , [math]\ldots[/math] , [math]s_[/math] , поэтому наша схема будет работать верно.
Читайте также: