Изменения

{{Определение|definition='''Шифратор''' (англ. ''encoder'') — [[Реализация булевой функции схемой из функциональных элементов| логическая схема]], имеющая <tex>2^n</tex> входов <tex>s_0</tex>, <div style="backgroundtex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{2^n -color: #ABCDEF; font1}</tex> и <tex>n</tex> выходов <tex>z_0</tex>, <tex>z_1</tex>, <tex>\ldots</tex>, <tex>z_{n-size: 16px; font1}</tex>. Если на <tex>i</tex>-weight: bold; color: #000000; text-align: center; padding: 4px; borderый вход <tex>s_i</tex> подать <tex>1</tex>, а на остальные входы — <tex>0</tex>, то выходы <tex>z_0</tex>, <tex>z_1</tex>, <tex>\ldots</tex>, <tex>z_{n-style: solid; border-width: 1px;">Эта статья находится в разработке!1}</divtex>будут кодировать число <includeonlytex>[[Категория: В разработке]]i</includeonlytex>.}}

|definition='''Дешифратор''' (англ. ''decoder'') — логическая схема, имеющая <tex>n</tex> входов <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{n- логический элемент1}</tex> и <tex>2^n</tex> выходов <tex>z_0</tex>, <tex>z_1</tex>, <tex>\ldots</tex>, получающий на вход $<tex>z_{2^n$-значное число $x$ в двоичном представлении и выводящий $1$ на $x$-м выходе}</tex>. На все остальные выходы выдаёт элемент выдаёт $подаётся <tex>0$.</tex>, кроме выхода <tex>z_i</tex>, на который подаётся <tex>1</tex>, где <tex>i</tex> — число, которое закодировано входами <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{n-1}</tex>

==Принцип работышифратора==Для начала разберёмся, как работает дешифратор 2[[File:4-to-2encoder.png|thumb|180px|Шифратор 4 (это значит-to-2]] Принцип работы шифратора заключается в том, что у этого дешифратора есть два входа $s_0$ и $s_1$ и четыре выхода $выходы <tex>z_0$</tex>, $<tex>z_1$</tex>, $z_2$ и $z_3$). Если $<tex>\ldots</tex>, <tex>z_{n-1}</tex> кодируют один из входов <tex>s_0 = </tex>, <tex>s_1 = 0$</tex>, <tex>\ldots</tex>, <tex>s_{2^n-1}</tex> в двоичной системе счисления. Очевидно, то что если подать на выходе $z_0$ будет несколько входов значение $<tex>1$</tex>, на остальных выходах то такая схема будет $0$работать некорректно. В качестве примера рассмотрим шифратор <tex>4</tex>-to-<tex>2</tex>. Если же $<tex>s_0 = 1$ и $s_1 = 0$</tex>, то на выходе $<tex>z_0 = z_1$ будет $1$, на остальных выходах будут $0$. Если $s_0 = 0$ и $s _1 = 1$, то на выходе $z_2$ будет $1$</tex>, а на остальных входах будет $0$. Если если же $s_0 = <tex>s_1 = 1$</tex>, то на выходе $z_3$ будет $<tex>z_0 = 1$, а на других - $</tex> и <tex>z_1 = 0$</tex>. Для более лучшего понимания обратимся к таблице истинностиОстальные случаи разбираются аналогичным образом.

|-align="center"! $<tex>S_0$ </tex> !! $<tex>S_1$ </tex> !! $Z_0$ <tex>S_2</tex> !! $Z_1$ <tex>S_3</tex> !! $Z_2$ <tex>Z_0</tex> !! $Z_3$<tex>Z_1</tex>|-align="center"| '''0''' <tex>\textbf{1}</tex> || '''<tex>0''' </tex> || '''1''' <tex>0</tex> || <tex>0 </tex> || <tex>0 </tex> || <tex>0</tex>|-align="center"| '''<tex>0</tex> || <tex>\textbf{1''' }</tex> || '''<tex>0''' </tex> || <tex>0 </tex> || '''1''' || <tex>0 </tex> || 0<tex>1</tex>|-align="center"| '''<tex>0''' </tex> || '''1''' <tex>0</tex> || 0 <tex>\textbf{1}</tex> || <tex>0 </tex> || '''<tex>1''' </tex> || <tex>0</tex>|-align="center"| '''1''' <tex>0</tex> || '''1''' <tex>0</tex> || <tex>0 </tex> || 0 <tex>\textbf{1}</tex> || 0 <tex>1</tex> || '''<tex>1'''</tex>

==Логическая схемашифратора== Построить логическую схему шифратора можно следующим образом: давайте будем использовать гейт <tex>OR</tex>, который имеет <tex>m</tex> входов (где <tex>m</tex> — какое-то натуральное число), и на выходе возвращает <tex>0</tex>, если на всех его входах будет подано <tex>0</tex>, в противном случае этот гейт вернёт <tex>1</tex>. Давайте рядом с каждым выходом <tex>z_i</tex> поставим гейт <tex>OR</tex>, и будем, по необходимости, расширять этот гейт. Тогда для каждого входа рассмотрим двоичное представление номера этого входа, и если на <tex>i</tex>-ом месте стоит <tex>1</tex>, то соединим этот вход с гейтом <tex>OR</tex>, который соединён с выходом <tex>z_i</tex>. Очевидно, если подать ровно на один вход <tex>1</tex>, то выходы будут кодировать это число в двоичном представлении (если подать <tex>1</tex> на вход <tex>s_0</tex>, то на всех выходах будет <tex>0</tex>, а сам вход не будет соединён ни с каким гейтом). {||[[Файл:LogicSircuit2to1encoder.png|thumb|360px|Логическая схема шифратора <tex>2</tex>-to-<tex>1</tex>]]|[[Файл:LogicSircuit4to2encoder.png|thumb|360px|Логическая схема шифратора <tex>4</tex>-to-<tex>2</tex>]]|} ==Принцип работы дешифратора== [[Файл:2to4decoder.png|thumb|180px|Дешифратор <tex>2</tex>-to-<tex>4</tex>]] Суть дешифратора заключается в том, что с помощью <tex>n</tex> входов <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{n-1}</tex> можно задавать выход, на который будет подаваться <tex>1</tex>. Для того, чтобы лучше понять, как работает дешифратор, рассмотрим в качестве примера дешифратор <tex>2</tex>-to-<tex>4</tex> (это значит, что у этого дешифратора есть два входа <tex>s_0</tex> и <tex>s_1</tex> и четыре выхода <tex>z_0</tex>, <tex>z_1</tex>, <tex>z_2</tex> и <tex>z_3</tex>). Если <tex>s_0 = s_1 = 0</tex>, то на выходе <tex>z_0</tex> будет значение <tex>1</tex>, на остальных выходах будет <tex>0</tex>. Если же <tex>s_0 = 1</tex>, <tex>s_1 = 0</tex>, то на выходе <tex>z_1</tex> будет <tex>1</tex>, на остальных выходах будут <tex>0</tex>. Если <tex>s_0 = 0</tex>, <tex>s _1 = 1</tex>, то на выходе <tex>z_2</tex> будет <tex>1</tex>, а на остальных входах будет <tex>0</tex>. Если же <tex>s_0 = s_1 = 1</tex>, то на выходе <tex>z_3</tex> будет <tex>1</tex>, а на других — <tex>0</tex>. {| class="wikitable"|-align="center"! <tex>S_0</tex> !! <tex>S_1</tex> !! <tex>Z_0</tex> !! <tex>Z_1</tex> !! <tex>Z_2</tex> !! <tex>Z_3</tex>|-align="center"| <tex>\textbf{0}</tex> || <tex>\textbf{0}</tex> || <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>0</tex> || <tex>0</tex>|-align="center"| <tex>\textbf{1}</tex> || <tex>\textbf{0}</tex> || <tex>0</tex> || <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>0</tex>|-align="center"| <tex>\textbf{0}</tex> || <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>0</tex> || <tex>\textbf{1}</tex> || <tex>0</tex>|-align="center"| <tex>\textbf{1}</tex> || <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>0</tex> || <tex>0</tex> || <tex>\textbf{1}</tex>|} ==Логическая схема дешифратора== Давайте построим логическую схему дешифратора рекурсивным способом: допустим, что мы построили схему для <tex>n-1</tex> входа, теперь попробуем слить <tex>n</tex>-ый выход с предыдущими <tex>n-1</tex>. Для <tex>n=1</tex> схема выглядит тривиальным образом: от входа <tex>s_0</tex> отходят два провода, один напрямую соединён с выходом <tex>z_1</tex>, другой соединён с гейтом <tex>NOT</tex>, а гейт <tex>NOT</tex> соединён с выходом <tex>z_0</tex>. Теперь допустим, что мы можем построить схему для <tex>n-1</tex> входов. Тогда <tex>n</tex>-ый вход соединим с дешифратором <tex>1</tex>-to-<tex>2</tex>, а первые <tex>n-1</tex> входы соединим с дешифратором <tex>(n-1)</tex>-to-<tex>(2^{n-1})</tex> и потом соединим каждый выход дешифратора <tex>(n-1)</tex>-to-<tex>(2^{n-1})</tex> с каждым выходом дешифратора <tex>1</tex>-to-<tex>2</tex> с помощью гейтов <tex>AND</tex>, потом соединим соответствующие гейты с выходами <tex>z_i</tex> таким образом, чтобы значение на входе <tex>z_i</tex> было равно <tex>1</tex> только в том случае, если число <tex>i</tex> кодируется входами <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{n-1}</tex>. Очевидно, что мы таким образом перебрали всевозможные комбинации значений на входах <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{n-1}</tex>, поэтому наша схема будет работать верно. {||[[Файл:LogicSircuit1to2decoder.png|thumb|360px|Логическая схема дешифратора <tex>1</tex>-to-<tex>2</tex>]]|[[Файл:LogicSircuit2to4decoder.png|thumb|180px360px|Логическая схема дешифратора <tex>2</tex>-to-<tex>4</tex>]]|} ==Использование в реальной жизни==Принцип работы дешифратора используется при построении [[Мультиплексор|мультиплексора и демультиплексора]]. Также шифраторы и дешифраторы используются в том случае, когда надо передавать большое количество данных, при этом использовать много проводов затруднительно (к примеру телеграф). В этом случае они позволяют использовать малое количество проводов, обеспечивая при этом наибольшее возможное количество состояний, которое может быть передано. ==См. также==*[[Реализация булевой функции схемой из функциональных элементов]]*[[Метод Лупанова синтеза схем]]*[[Мультиплексор и демультиплексор]] ==Источники информации==*[https://en.wikipedia.org/wiki/Priority_encoder Wikipedia - Priority encoder]*[https://en.wikipedia.org/wiki/Binary_decoder Wikipedia - Binary decoder]*[https://www.efxkits.us/different-types-encoder-decoder-applications Different Types of Encoder and Decoder and Its Uses] [[Категория: Дискретная математика и алгоритмы]]

Построить схему дешифратора не очень сложно. Действительно, для того, чтобы точно определить, какой из выходов закодирован входами $s_0$, $s_1$, $\ldots$, $s_{n-1}$. Давайте переберём всевозможные варианты входов. Всего всевозможных вариантов подать значения на входы $2^n$. Давайте будем строить такую схему рекурсивным способом, т.е. сначала построим схему для $n-1$ элемента, а потом сольём $n$-ый элемент с $n-1$ элементами. Допустим, что $n = 1$. Тогда очевидно, что всевозможных вариантов всего два: $s_0 = 0$ или $s_0 = 1$. Давайте от входа $s_0$ мы выведем два провода, один из них, пока, не будем трогать, а другой соединим с гейтом $NOT$. Если количество входов было равно одному, то мы перебрали всевозможные варианты, т.е. давайте соединим провод без гейта $NOT$ с выходом $Z_0$, а с гейтом $NOT$ - с выходом $z_1$. Допустим, что $n \geqslant 1$. Тогда допустим, что мы построили такую схему для $n-1$ элемента, что для всевозможных значений первых $n-1$ у нас есть $2^{n-1}$ проводов, причем при любых значений на первых $n-1$ входах только у одного провода будет на выходе $1$, на остальных будет $0$. Давайте тогда и от входа $n$ таким же образом проведём два провода[[Категория: один Схемы из них будет без гейта $NOT$, а другой будет с гейтом. Поставим еще $2^n$ гейтов $AND$, первые $2^{n-1}$ гейтов будут соединять провода с $2^{n-1}$ проводами от дешифратора на $n-1$ вход и напрямую вход $s_n$. Другие же $2^{n-1}$ гейтов $AND$ будут также соединять провода со схемой для $n-1$ входа и гейт $NOT$, который подсоединён со входом $s_n$. Таким образом, у нас на выходе получается $2^n$ проводов, на концах которых при любых значениях на входах $s_0$, $s_1$, $\ldots$, $s_{n-1}$ будут все $0$ кроме того провода, номер которого кодируют эти самые входы. И в конце на выходы подадим соответствующие им провода.функциональных элементов ]]