---
title: Cryptography(Decoding&Encoding)
tags: Cryptography
language: zh-tw
---
# Cryptography(Decoding&Encoding)
:::warning
<div class=display >
</div>
<div class=display>
<font size=5px color=#E2C2DE>
<strong>Cryptography(Decoding&Encoding)</strong>
</font>
</br>
<img src= "https://i.imgur.com/MoNFm7S.png" weight=300 height=300>
</br>
<font size=5px color=#E2C2DE>
<strong>Presented by J.Tsai</strong>
</font>
</div>
<style>
.display {
text-align:center;
}
</style>
:::
---
## 9/11(Fri.)
### 1.(simple)
:::success
Apple $\to$ 00
Banana $\to$ 01
Cherry $\to$ 10
Grape $\to$ 11
:::
If there is a mistake. The message will be wrong.
### 2.(common)
:::success
00 $\to$ 000
01 $\to$ 001
10 $\to$ 101
11 $\to$ 110
:::
It is not enough secure.
### 3.(advanced)
:::success
00 $\to$ 00000
01 $\to$ 01111
10 $\to$ 10110
11 $\to$ 11001
:::
first two code can help us sort the four fruits.
If there are few mistakes. The way is good.
### frame of decoding and encoding
:::info
source $\to$ encoder $\to$ channel $\to$ decoder $\to$ receiver
:::
If there is a "noise" in channel. It will be a wrong message.
So, we need a channel decoder and channel encoder
:::info
source $\to$ encoder $\to$ channel encoder $\to$ channel $\to$ channel decoder $\to$ decoder $\to$ reciver
:::
**Maximum Likelihood Estimations (MLE)**
Maximum likelihood estimation (MLE) is a method of estimating the parameters of a probability distribution by maximizing a likelihood function.
---
### Repeated encoder
:::success
1.String length= $k$
2.Repeat $(2r+1)$ times
3.ex: $k=2,r=2$ $(2r+1=5)$
$00 \to 0000000000$
$01 \to 1010101010$
$01 \to 0101010101$
$11 \to 1111111111$
If received message =$1111100000$
Choose the better one(the fewest mistakes 00)
But, it is too large and too slow (2bits $\to$ 10bits)
:::
You need to analysis the "Hamming distance" between every messages.
### book suggestion
Book: *First Course of Coding Theory*
## 9/18(Fri.)
### probability
:::info
*If you trust Mechanism. You may not trust "Probability theory".*
:::
After the publishment of "Quantum Mechanics", Probability theory have been used in physical and mathematical commonly.
Thus, we made a kind of Mathematical Model called **"Statistical model"**.
1.We collect all possible outcomes and call it "sample space",
S= {all possible outcomes} **P.S: sample space is finite.**
2.event $A\leq S$
3.event space $Σ$=$\{all$ $events\}$
example: tossing a coin
$S\{H,T\}:=2^S$(Power Set)
$\Sigma=\{\phi,\{H\},\{T\},\{H,T\}\}$
***Pierre-Simon marquis de Laplace**
---
### DEF:(classical probability)
**(in classical probability,we assume sample space($S$) is finite.)**
:::success
property:
if $A,B \in \Sigma$ and $A \cap B \in \Sigma$
then $P(A \cup B)=P(A)+P(B)$
$P(A \cup B):=n(A \cup B)/n\{S\}$
$=n(A)+n(B)+n(A \cap B)/n(s)$
$=n(A)/n(S)+n(B)/n(S)
=P(A)+P(B)$
In this condition,we assume $n(A \cap B)=0$
:::
:::success
§probability:
definition(conditional probability)
Given an event $B \in \Sigma$ with $P(B)>0$, then define the probability of A given B as
$P(A|B):=n(A∩B)/n(B)=(n(A∩B)/n(s))/(n(b)/n(s))=P(A∩B)/P(B)$
:::
## 9/25(Fri.)
### Recall:(conditional probability)
Given an event $B \in \Sigma$ with $P(B)>0$, then define $P(A|B)=P(A \cap B)/P(B)$
:::success
**Definition:(independing)**
$P(A|B)=P(A) \Longleftrightarrow P(A∩B)/P(B)=P(A) \Longleftrightarrow P(A∩B)=P(A)P(B)$
"$P(A∩B)=P(A)P(B)$" It still works when $B$=0. Therefore, the third equation is better.
**$A$ and $B$ are independent** $\Longleftrightarrow P(A∩B)=P(A)P(B)$
:::
### Recall:(Laplace's probablility)
$P:$
$\Sigma \longrightarrow [0,1]$
$A \longmapsto P(A)=n(A)/n(S)$
probability:
(1)$n(S)=1$
(2)If $A \cap B=\phi$ ,then $P(A \cup B)=P(A)+P(B)$
:::success
**Definition:(independing):(kolmogorov's axioms)**
1.Sample apace:$S=\{all$ $outcomes\}$
Event space:$Σ$
2.$\Sigma\longrightarrow[0,1]$ is a probability function if it satisfies:
(1)$P(S)$=1
(2)$A_i \cup a_j$ =$\phi$ if $i\neq j$,then
$\Rightarrow {P(\cup_{i=1}^\infty Ai)}=\sum_{i=1}^\infty{P(Ai)}$
:::
### Example(Bernoulli trial with p)
:::success
* $Sample$ $space=\{success,failure\},abbr. \{S,F\}$
* $P:$
$\Sigma \longrightarrow [0,1]$
$\phi \longmapsto 0$
$\{S\} \longmapsto p$
$\{F\} \longmapsto q=(p-1)$
$\{S,F\} \longmapsto 1$
:::
### Def:
(1)Code alphabat $A=\{a_1,a_2,...,a_n\}(\{0,1\})$
(2)$w=w_1,w_2,...w_n$ with $w_i \in A$ $(000,111)$
n=length
(3)$C:=\{all$ $code$ $words\}(c\{000,001,101,111\})$
$n(C)$=M=size
(4)$A$ and $C$ with length=$n$,size=$M$ is an $(n,M)-code$
**example:**
Code alphabat $A=\{0,1\}$
(1)$C1=\{00,01,10,11\}$ is an$(2,4)-code$
(2)$C2=\{0011,0101,1010,1100,1001,0110\}$ is an $(4,6)-code$
**Definition:**
(1)Foward probability $P$ satisfies:
$\sum_{j=1}^qP(a_j$ $received|a_i$ $sent$)$=1$
(2)The channel is memoryless.
If $Ｘ=x_1x_2...x_n$ ,then$Ｃ=c_1c_2,c_n$
$P(X$ $received|C$ $sent)=\prod_{i=1}^nP(X_i$ $received|C_i$ $sent)$
## 9/26(Sat.)
### Definition(recall):
:::success
(1)Precedent probability P satisfies:
$\sum_{j=1}^nP(a_j$ $received|a_j$ $sent)=1$
:::
:::success
(2)The channel is memoryless.
if $Ｘ=x_1x_2...x_n$ ,then
$Ｃ=c_1,c_2,...,c_n$
$P(X$ $received|C$ $sent)=\prod_{k=1}^nＰ(X_ｋ received|C_ｋ sent)$
:::
:::success
(3)The channel is symmetric when it satisfy the two conditions.
1.each symbol transmitted has the same probability $p<1/2$ of being received.
2.If a symbol is received in error, then each of the $(n-1)$ possible. errors is equally likely.
:::
:::success
(4)Binary Symmetric Code(BSC)
* the channel is memoryless and symmetric.
* $P(1 received|0 sent)=P(0received|1 sent)=p$
* $P(1 received|1 sent)=P(0received|0 sent)=1-p$
:::
### Example
* $P\{110\}$ over **BSC**
* crossover probability $p=0.05$
* received code is 110
$P(110$ $received|000$ $sent)=(0.05)*(0.05)*(0.95)=0.002375$
$P(110$ $received|111$ $sent)=(0.95)*(0.95)*(0.05)=0.045125$
Compare the two probabilities, we can conclude the 111 is more likely to be the codes sent.
### Maximum Likelihood Decoding
$C_{i=1}^n=\{c_i\}$ is a code of the length $n$. if the received code is $x$, then it will be decoded to $C_x$,which satisfies:
$P(X$ $received|C_x$ $sent)=max$ $P(X$ $received|C$ $sent)$.
### Exercise:
::: info
In order to estimate the amount of birds of a special species, the researchers had captured 10 birds and marked them. Then, they let them fly back. After a period of time, the researchers recaptured(randomly) 20 birds and found one of this species were in the forest the most likely?
:::
:::spoiler answer(picture)
* 10 is marked and captive.
* Recapture 20 birds, and one of them is marked.
* Suppose those exist n birds$(n\geq 29)$, and the probability of the above events is
$C_1^{10}xC_{19}^{n-10}/C_{20}^n$, denoted as $P_n$.
* To estimate $P_n$, we calculate the ratio $P_{n+1}/P_n:$
---
**p.s.:**
$n,p \in N,n>=p$
(1)$n!=^{def} n*(n-1)*(n-2)*...*2*1$
(2)$C_p^n=^{def} n!/(n-p)!p!$
:::
## 11/6(Fri.)
### Hamming distance
:::spoiler about Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming.
:::
### Motivation
Consider codes sent over a BSC with crossover probability $p<1/2$:
$\because P(X$ $received|C$ $sent)=p^e*(1-p)^{n-e}$, where $n$ is the length of codes and $e$ is the number of places at which $X$ differs from $C$,and $p <(1-p)$.
$\therefore P(X$ $received|C$ $sent) larger \iff (n-e) larger\iff e smaller$
### Defnition:
Suppose $X$,$Y$ be two strings of length $n$ over an alphabet A. The hamming distance from $X$ to $Y$, denoted as $d(X,Y)$, defined as
$d(X,Y):=\sum_{k=1}^nd(x_k,y_k)$,where
$d(x_k,y_k)=$
$1$ $if$ $x_k \neq y_k$
$0$ $if$ $x_k = y_k$
### Example:
Suppose $A=\{0,1\}$,$X=01010$,$Y=11111$,$Z=00000$
$d(X,Y)=\sum_{i=1}^5d(x_i,y_i)=3$
$d(X,Z)=\sum_{i=1}^5d(x_i,z_i)=2$
$d(Y,Z)=\sum_{i=1}^5d(y_i,z_i)=5$
### Property
For a fixed length $n$, the Hamming distance is a metric on the set of the words of length $n$ (also known as a Hamming space), as it fulfills the conditions of non-negativity, symmetry, the Hamming distance of two words is 0 if and only if the two words are identical, and it satisfies the triangle inequality as well:
**pf:Hamming distance satisfy Triangle Inequality**
Now, we assume three strings, $X, Y, Z$, and their length is $n$.
**Consider $X_k,Y_k,Z_k \in A$:**
(1)If $X_k=Z_k$, then $d(X_k,Y_k)=0$
**$\Rightarrow d(X_k,Z_k) \leq d(X_k,Y_k)+d(Y_k,Z_k)$**
(2)If $X_k \neq Z_k$, then $X_k \neq Y_k$ or $Y_k \neq Z_k$
Thus, **$d(X_k,Z_k) \leq d(X_k,Y_k)+d(Y_k,Z_k)$**
$\therefore d(X,Z)=\sum_{i=1}^n d(X_k,Z_k) \leq \sum_{i=1}^n[d(X_k,Y_k)+d(Y_k,Z_k)]=d(X,Z)+d(Y,Z)$
---
## Sources of Information
**Maximum Likelihood Estimations(MLE):**
https://en.wikipedia.org/wiki/Maximum_likelihood_estimation
**Bernoulli trial:**
https://en.wikipedia.org/wiki/Bernoulli_trial
**Binary symmetric channel(BSC):**
https://en.wikipedia.org/wiki/Binary_symmetric_channel
**Hamming distance:**
https://en.wikipedia.org/wiki/Hamming_distanc
Sign in with Wallet
Connect another wallet