Coding theory: Difference between revisions

Revision as of 06:34, 11 January 2021

Revision as of 00:14, 2 February 2021

Line 37:

===Definition===

Data can be seen as a [[random variable]] <math>X:\Omega\rightarrowto\mathcal{X}</math>, where <math>x \in \mathcal{X}</math> appears with probability <math>\mathbb{P}[X=x]</math>.

Data are encoded by strings (words) over an [[Alphabet (computer science)|alphabet]] <math>\Sigma</math>.

Line 43:

A code is a function

:<math>C:\mathcal{X}\rightarrowto\Sigma^*</math> (or <math>\Sigma^+</math> if the empty string is not part of the alphabet).

<math>C(x)</math> is the code word associated with <math>x</math>.

Line 49:

Length of the code word is written as

:<math>l(C(x)).</math>.

Expected length of a code is

:<math>l(C) = \sum_{x\in\mathcal{X}}l(C(x))\mathbb{P}[X=x] .</math>

The concatenation of code words <math>C(x_1,... \ldots, x_k) = C(x_1)C(x_2)... \cdots C(x_k)</math>.

The code word of the empty string is the empty string itself:

:<math>C(\epsilon) = \epsilon</math>

===Properties===

# <math>C:\mathcal{X}\rightarrowto\Sigma^*</math> is [[Variable-length code#Non-singular codes|non-singular]] if [[Injective function|injective]].

# <math>C:\mathcal{X}^*\rightarrowto\Sigma^*</math> is [[Uniquely decodable code#Uniquely decodable codes|uniquely decodable]] if injective.

# <math>C:\mathcal{X}\rightarrowto\Sigma^*</math> is [[Variable-length code#Prefix codes|instantaneous]] if <math>C(x_1)</math> is not a prefix of <math>C(x_2)</math> (and vice versa).

===Principle===

Line 74:

===Example===

[[FAX|Facsimile]] transmission uses a simple [[Run-length encoding|run length code]]. Source coding removes all data superfluous to the need of the transmitter, decreasing the bandwidth required for transmission.

Source coding removes all data superfluous to the need of the transmitter,

decreasing the bandwidth required for transmission.

==Channel coding==