Шифратор и дешифратор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метки: правка с мобильного устройства, правка из мобильной версии)
м (rollbackEdits.php mass rollback)
 
(не показано 67 промежуточных версий 2 участников)
Строка 1: Строка 1:
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
+
{{Определение
<includeonly>[[Категория: В разработке]]</includeonly>
+
|definition='''Шифратор''' (англ. ''encoder'') — [[Реализация булевой функции схемой из функциональных элементов| логическая схема]], имеющая <tex>2^n</tex> входов <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{2^n - 1}</tex> и <tex>n</tex> выходов <tex>z_0</tex>, <tex>z_1</tex>, <tex>\ldots</tex>, <tex>z_{n-1}</tex>. Если на <tex>i</tex>-ый вход <tex>s_i</tex> подать <tex>1</tex>, а на остальные входы — <tex>0</tex>, то выходы <tex>z_0</tex>, <tex>z_1</tex>, <tex>\ldots</tex>, <tex>z_{n-1}</tex> будут кодировать число <tex>i</tex>.
 +
}}
  
 
{{Определение
 
{{Определение
|definition='''Дешифратор''' (англ. ''decoder'') - логический элемент, имеющий $n$ входов $s_0$, $s_1$, $\ldots$, $s_{n-1}$ и $2^n$ выходов $z_0$, $z_1$, $\ldots$, $z_{2^n-1}$. На все выходы подаётся $0$, кроме выхода $z_i$, на который подаётся $1$, где $i$ - число, которое закодировано входами $s_0$, $s_1$, $\ldots$, $s_{n-1}$
+
|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-1}</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>
 
}}
 
}}
  
==Принцип работы==
+
==Принцип работы шифратора==
Суть дешифратора заключается в том, что с помощью $n$ входов $s_0$, $s_1$, $\ldots$, $s_{n-1}$ можно управлять, на какой выход будет подаваться $1$. Для того, чтобы лучше понять, как работает дешифратор, рассмотрим дешифратор 2-to-4 (это значит, что у этого дешифратора есть два входа $s_0$ и $s_1$ и четыре выхода $z_0$, $z_1$, $z_2$ и $z_3$). Если $s_0 = s_1 = 0$, то на выходе $z_0$ будет значение $1$, на остальных выходах будет $0$. Если же $s_0 = 1$ и $s_1 = 0$, то на выходе $z_1$ будет $1$, на остальных выходах будут $0$. Если $s_0 = 0$ и $s _1 = 1$, то на выходе $z_2$ будет $1$, а на остальных входах будет $0$. Если же $s_0 = s_1 = 1$, то на выходе $z_3$ будет $1$, а на других - $0$. Для более ясной картины обратимся к таблице истинности.
+
 
 +
[[File:4-to-2encoder.png|thumb|180px|Шифратор 4-to-2]]
 +
 
 +
Принцип работы шифратора заключается в том, что выходы <tex>z_0</tex>, <tex>z_1</tex>, <tex>\ldots</tex>, <tex>z_{n-1}</tex> кодируют один из входов <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{2^n-1}</tex> в двоичной системе счисления. Очевидно, что если подать на несколько входов значение <tex>1</tex>, то такая схема будет работать некорректно. В качестве примера рассмотрим шифратор <tex>4</tex>-to-<tex>2</tex>. Если <tex>s_0 = 1</tex>, то <tex>z_0 = z_1 = 0</tex>, если же <tex>s_1 = 1</tex>, то <tex>z_0 = 1</tex> и <tex>z_1 = 0</tex>. Остальные случаи разбираются аналогичным образом.
  
 
{| class="wikitable"
 
{| class="wikitable"
|-
+
|-align="center"
! $S_0$ !! $S_1$ !!  $Z_0$ !! $Z_1$ !! $Z_2$ !! $Z_3$
+
! <tex>S_0</tex> !! <tex>S_1</tex> !!  <tex>S_2</tex> !! <tex>S_3</tex> !! <tex>Z_0</tex> !! <tex>Z_1</tex>
|-
+
|-align="center"
| '''0''' || '''0''' || '''1''' || 0 || 0 || 0
+
| <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>0</tex> || <tex>0</tex> || <tex>0</tex> || <tex>0</tex>
|-
+
|-align="center"
| '''1''' || '''0''' || 0 || '''1''' || 0 || 0
+
| <tex>0</tex> || <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>0</tex> || <tex>0</tex> || <tex>1</tex>
|-
+
|-align="center"
| '''0''' || '''1''' || 0 || 0 || '''1''' || 0
+
| <tex>0</tex> || <tex>0</tex> || <tex>\textbf{1}</tex> || <tex>0</tex> || <tex>1</tex> || <tex>0</tex>
|-
+
|-align="center"
| '''1''' || '''1''' || 0 || 0 || 0 || '''1'''
+
| <tex>0</tex> || <tex>0</tex> || <tex>0</tex> || <tex>\textbf{1}</tex> || <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>]]
 
|}
 
|}
  
==Логическая схема==
+
==Принцип работы дешифратора==
[[Файл:LogicSircuit2to4decoder.png|thumb|180px|Логическая схема дешифратора 2-to-4]]
 
  
Давайте переберём всевозможные варианты значений на входах. Поскольку у нас $n$ входов, то отсюда следует, что всевозможных вариантов - $2^n$. Давайте будем строить такую схему рекурсивным способом, т.е. сначала построим дешифратор для $n-1$ элемента, а потом сольём $n$-ый элемент с $n-1$ элементами. Допустим, что $n = 1$. Тогда очевидно, что всевозможных вариантов всего два: $s_0 = 0$ или $s_0 = 1$. Давайте от входа $s_0$ мы выведем два провода, один из них, пока, не будем трогать, а другой соединим с гейтом $NOT$. Если количество входов было равно $1$, то мы перебрали всевозможные варианты, т.е. давайте соединим провод без гейта $NOT$ с выходом $z_0$, а с гейтом $NOT$ - с выходом $z_1$. Допустим, что $n \geqslant 2$. Тогда допустим, что мы построили дешифратор для $n-1$ элемента. Теперь сольём $n$-ый вход с дешифратором для $n-1$ входов. У такого дешифратора $2^{n-1}$ выходов. У входа $s_{n-1}$ может быть два варианта значений: $0$ и $1$. Давайте поставим $2^n$ гейтов $AND$ и соединим эти гейты соответственно с выходами дешифратора ${n-1}$-to-${2^{n-1}}$.
+
[[Файл: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|360px|Логическая схема дешифратора <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]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
  
==Источники информаци==
+
[[Категория: Схемы из функциональных элементов ]]
*[https://en.wikipedia.org/wiki/Binary_decoder Binary decoder]
 

Текущая версия на 19:06, 4 сентября 2022

Определение:
Шифратор (англ. encoder) — логическая схема, имеющая [math]2^n[/math] входов [math]s_0[/math], [math]s_1[/math], [math]\ldots[/math], [math]s_{2^n - 1}[/math] и [math]n[/math] выходов [math]z_0[/math], [math]z_1[/math], [math]\ldots[/math], [math]z_{n-1}[/math]. Если на [math]i[/math]-ый вход [math]s_i[/math] подать [math]1[/math], а на остальные входы — [math]0[/math], то выходы [math]z_0[/math], [math]z_1[/math], [math]\ldots[/math], [math]z_{n-1}[/math] будут кодировать число [math]i[/math].


Определение:
Дешифратор (англ. decoder) — логическая схема, имеющая [math]n[/math] входов [math]s_0[/math], [math]s_1[/math], [math]\ldots[/math], [math]s_{n-1}[/math] и [math]2^n[/math] выходов [math]z_0[/math], [math]z_1[/math], [math]\ldots[/math], [math]z_{2^n-1}[/math]. На все выходы подаётся [math]0[/math], кроме выхода [math]z_i[/math], на который подаётся [math]1[/math], где [math]i[/math] — число, которое закодировано входами [math]s_0[/math], [math]s_1[/math], [math]\ldots[/math], [math]s_{n-1}[/math]


Принцип работы шифратора

Шифратор 4-to-2

Принцип работы шифратора заключается в том, что выходы [math]z_0[/math], [math]z_1[/math], [math]\ldots[/math], [math]z_{n-1}[/math] кодируют один из входов [math]s_0[/math], [math]s_1[/math], [math]\ldots[/math], [math]s_{2^n-1}[/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{1}[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math]
[math]0[/math] [math]\textbf{1}[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]1[/math]
[math]0[/math] [math]0[/math] [math]\textbf{1}[/math] [math]0[/math] [math]1[/math] [math]0[/math]
[math]0[/math] [math]0[/math] [math]0[/math] [math]\textbf{1}[/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]2[/math]-to-[math]1[/math]
Логическая схема шифратора [math]4[/math]-to-[math]2[/math]

Принцип работы дешифратора

Дешифратор [math]2[/math]-to-[math]4[/math]

Суть дешифратора заключается в том, что с помощью [math]n[/math] входов [math]s_0[/math], [math]s_1[/math], [math]\ldots[/math], [math]s_{n-1}[/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{0}[/math] [math]\textbf{0}[/math] [math]\textbf{1}[/math] [math]0[/math] [math]0[/math] [math]0[/math]
[math]\textbf{1}[/math] [math]\textbf{0}[/math] [math]0[/math] [math]\textbf{1}[/math] [math]0[/math] [math]0[/math]
[math]\textbf{0}[/math] [math]\textbf{1}[/math] [math]0[/math] [math]0[/math] [math]\textbf{1}[/math] [math]0[/math]
[math]\textbf{1}[/math] [math]\textbf{1}[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]\textbf{1}[/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^{n-1})[/math] и потом соединим каждый выход дешифратора [math](n-1)[/math]-to-[math](2^{n-1})[/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_{n-1}[/math]. Очевидно, что мы таким образом перебрали всевозможные комбинации значений на входах [math]s_0[/math], [math]s_1[/math], [math]\ldots[/math], [math]s_{n-1}[/math], поэтому наша схема будет работать верно.

Логическая схема дешифратора [math]1[/math]-to-[math]2[/math]
Логическая схема дешифратора [math]2[/math]-to-[math]4[/math]

Использование в реальной жизни

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

См. также

Источники информации