\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Dot-Dash Code
Needed by:
Bit Strings
Prefix-Free Codes
Sheet PDF
Graph PDF



Can we generalize the idea of flash codes.1


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.


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

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). \]

We call an code uniquely decodable if its extension is injective. In other words, given the code $C(\xi )$ for a sequence $\xi \in \str(X)$, we can recover $\xi $. We call $C(\xi )$ the encoding of $\xi $. We call $\xi $ the decoding of $C(\xi )$.

  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. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view