Content deleted Content added
m Corrected small math typos |
→Setup: : typo |
||
Line 8:
# [[Hamming distance]] : Given two [[Euclidean vector|vector]]s <math>u, v\in\sum^n</math> the Hamming distance between u and v, denoted by <math>\Delta(u, v)</math>, is defined to be the number of positions in which u and v differ.
# Minimum distance : Let <math>C\subseteq\sum^n</math> be a [[code]]. The minimum distance of code C is defined to be <math>d = \min{\Delta(c_1, c_2)}</math> where <math>c_1 \ne c_2 \in C</math>
# Code concatenation : Given <math>m = (m_1, \ldots, m_K) \in [Q]^K</math>, consider two codes which we call outer code and inner code <math>C_\text{out} = [Q]^K \rightarrow [Q]^N, C_\text{in} : [q]^k \rightarrow [q]^n</math>, and their distances are <math>D</math> and <math>d</math>. A concatenated code can be achieved by <math>C_\text{out} \circ C_\text{in} (m) = (C_\text{in} (C_\text{out} (m)_1), \ldots, C_\text{in} (C_\text{out} (m)_N ))</math> where <math>C_\text{out}(m) = ((C_\text{out} (m)_1, \ldots, (m)_N ))</math>. Finally we will take <math>C_\text{out}</math> to be [[Reed Solomon|RS code]], which has an errors and erasure decoder, and <math>K = O(\log{N})</math>, which in turn implies that MLD on the inner code will be poly(<math>N</math>) time.
# Maximum likelihood decoding(MLD) : MLD is a decoding method for error correcting codes, which outputs the codeword closest to the received word in Hamming distance. The MLD function denoted by <math>D_{MLD} : \sum^n \rightarrow C</math> is defined as follows. For every <math>y\in\sum_n</math>, <math>D_{MLD}(y) = \arg \min_{c \in C}\Delta(c, y)</math>.
# [[Probability density function]] : A [[probability distribution]] <math>\Pr[\bullet]</math> on a sample space <math>S</math> is a mapping from events of <math>S</math> to [[real number]]s such that <math>\Pr[A] \ge 0</math> for any event <math>A</math>, <math>\Pr[S] = 1</math>, and <math>\Pr[A \cup B] = \Pr[A] + \Pr[B]</math> for any two mutually exclusive events <math>A</math> and <math>B</math>
|