Codierungstheorie

Definition:  Sei A ein Alphabet. Dann ist A* die Menge aller Wörter über A; ferner ist Aⁿ die Menge aller Wörter der Länge n über A. Das leere Wort wird mit ε bezeichnet, d.h. es gilt A⁰ = {ε}.

Definition:  Zwei Wörter u, v ∈ A* werden verkettet, indem sie zu einem Wort uv hintereinandergeschrieben werden. Für alle Wörter u ∈ A* gilt uε = εu = u.

Definition:  Sei u ein Wort über A und X = x₀, ..., x_k-1 eine endliche Folge von Wörtern über A. Das Produkt uX ist die endliche Folge

uX  =  ux₀, ..., ux_k-1,

d.h. die Folge uX entsteht, indem u mit jedem Wort x_i der Folge X verkettet wird.

Definition:  Sind X = x₀, ..., x_k-1 und Y = y₀, ..., y_m-1 zwei endliche Folgen, so ist X, Y die endliche Folge, die entsteht, wenn X und Y hintereinandergeschrieben werden:

X, Y  =  x₀, ..., x_k-1, y₀, ..., y_m-1

Definition:  Ist X = x₀, ..., x_k-1 eine endliche Folge, so ist X^R die endliche Folge, die entsteht, wenn X rückwärts durchlaufen wird:

X^R  =  x_k-1, ..., x₀