Content deleted Content added
No edit summary |
No edit summary |
||
Line 7:
# Hamming distance : Given two [[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}, ..., m_{K}) \in [Q]^K</math>, consider two codes which we call outer code and inner code <math>C_{out} = [Q]K \rightarrow [Q]N, C_{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_{out} \circ C_{in} (m) = (C_{in} (C_{out} (m)_1), \ldots, C_{in} (C_{out} (m)_N ))</math> where <math>C_{out}(m) = ((C_{out} (m)_1, \ldots, (m)_N ))</math>. Finally we will take <math>C_{out}</math> to be [http://en.wikipedia.org/wiki/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>
| |||