Codes

Why

Can we generalize the idea of flash codes.¹

Definition

Let $X$ be a set and $A$ be an alphabet set. We denote the set of all finite sequences (strings) in $A$ by $\str(A)$. We read $\str(A)$ aloud as “the strings in $A$.” The length zero string is $\varnothing$.

A code for $X$ in $A$ is a function from $X$ to $\str(A)$. In this context, we refer to the finite set $A$ as an alphabet and we call $c(x)$ the codeword of $x$. The length of $x \in X$, with respect to a code $c: X \to \str(A)$, is the length of the sequence $c(x)$ (its codeword). We call a code nonsingular if it is injective.

Examples

Define $c: \set{\alpha , \beta } \to \set{0, 1}$ by $c(\alpha ) = (0,)$ and $c(\beta ) = (1,)$.²

Code extensions

Let $s,t \in \str(A)$ of length $m$ and $n$ respectively. The concatenation of $s$ with $t$ is the length $m+n$ string $u \in \str(A)$ defined by $u_{1} = s_1, \dots , u_m = s_m$ and $u_{m+1} = t_1, \dots , u_{m+n} = t_n$. We denote the concatenation of $s$ and $t$ by $st$. Note, however, that $st \neq ts$, although $s(tr) = (st)r$.

Given a code $c: X \to \str(A)$, we can produce a code for $\str(X)$ in a natural way. The extension of $c$ is the function $C: \str(X) \to \str(A)$ defined, for $\xi = (\xi _1, \dots , \xi _n) \in \str(X)$, by

\[ C(\xi ) = c(\xi _1) \cdots c(\xi _n). \]

1. The reliance of this sheet on Flash CodesandDot-Dash Codesis for this justification, and not for any of the terms presented. ↩︎
2. Future editions will include additional examples. ↩︎