基本概念

Alphabet 字母表

Defn. Alphabet is just another name for “finite set”.

Defn. An Alphabet $Q$ determines a new set $Q^*$, which contains all finite sequences of elements in $Q$. The elements in $Q^$ are called codewords (on Q). i.e., $$ Q^ := \bigcup_{i \in \mathbb{N}_+} Q^i $$

NOTE.

1. Alphabet 中的元素可以是任何东西！比如：

   $S$ := {“dogs”, “cats”, “birds”}，(含有待编码的东西，“source alphabet”)

   $T$ := {0, 1}, (含有用来编码的符号, “target alphabet”)

   $T^*$ := {00, 01, 10, 11}，(含有编码后的东西, “codewords”)

2. source alphabet 中的元素一般称为 clear text，target alphabet $Q$ 中的元素一般称为 letters, Q* 中的元素是 codewords。

3. codewords 有等长和不等长之分。

Defn. Let $S$ and $T$ be alphabets, 编码(code)是一个从 $S$ 到 $T^*$ 的映射，i.e. code: $S \to T^*$.

NOTE.

1. 但是我们一般认为 $T^*$ 中的元素才是 code 而不是映射本身，这有点像随机变量一般认为是 $\tilde{\Omega}$ 中的元素而不是可测映射本身。

2. Ex. $Q := {0, 1}$, $\mathbf{c} = 00100 (\equiv (0, 0, 1, 0, 0)) \in Q^*$，$\mathbf{c}$ 称为 2-ary code of length 5.

Hamming Space 汉明空间

Defn. 设 $Q$ 是 alphabet, $N \in \mathbb{N}+$, 度量空间 $(Q^N, h_d)$ 称为 $Q$ 上的 Hamming space. $h_d: Q^N \times Q^N \to \mathbb{N}+$ 称为 Hamming distance, 定义为：

$$ \forall \mathbf{a}, \mathbf{b} \in Q^N, h_d(\mathbf{a}, \mathbf{b}) := # {i \in {1, 2, \ldots N} : a_i \neq b_i} $$