Content deleted Content added
Tom.Reding (talk | contribs) m Disambiguated: vector → Euclidean vector |
|||
Line 6:
==Setup==
# [[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.
| |||