1 |
dashley |
140 |
%$Header$ |
2 |
|
|
|
3 |
|
|
\chapter[\cedczeroshorttitle{}]{\cedczerolongtitle{}} |
4 |
|
|
|
5 |
|
|
\label{cedc0} |
6 |
|
|
|
7 |
|
|
\beginchapterquote{``True genius resides in the capacity for evaluation of uncertain, |
8 |
|
|
hazardous, and conflicting information.''} |
9 |
|
|
{Winston Churchill} |
10 |
|
|
\index{Churchill, Winston} |
11 |
|
|
|
12 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
13 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
14 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
15 |
|
|
\section{Introduction} |
16 |
|
|
%Section tag: INT0 |
17 |
|
|
\label{cedc0:sint0} |
18 |
|
|
|
19 |
|
|
In microcontroller work, it is frequently necessary to consider how |
20 |
|
|
best to add redundancy to data. The following design scenarios are |
21 |
|
|
common. |
22 |
|
|
|
23 |
|
|
\begin{enumerate} |
24 |
|
|
\item Immediately on powerup, a microcontroller product calculates |
25 |
|
|
the checksum of its program memory (usually ROM or FLASH) and compares this |
26 |
|
|
checksum to a stored value in order to detect possible corruption of program |
27 |
|
|
memory. What is the best way to calculate a checksum for this |
28 |
|
|
purpose? |
29 |
|
|
\item A storage medium that will tolerate a limited number of write cycles |
30 |
|
|
(such as EEPROM), will used to used to store data which will change |
31 |
|
|
and need to rewritten more times than the life of the medium will |
32 |
|
|
accomodate. As a result, a strategy which wears out a portion of the medium |
33 |
|
|
and then uses another portion is employed. When a portion of the medium |
34 |
|
|
wears out (as evidenced by corruption of bits), how can the data be |
35 |
|
|
reliably recovered before |
36 |
|
|
being transferred to the next portion? |
37 |
|
|
\item A microcontroller product stores data in battery-backed RAM while powered |
38 |
|
|
down. What type of checksum should be added to this data to provide the maximum |
39 |
|
|
protection against data corruption? |
40 |
|
|
\item Microcontrollers on the same circuit board communicate with each other |
41 |
|
|
using UARTs. What form of checksum should be used to add protection |
42 |
|
|
against electrical noise? |
43 |
|
|
\end{enumerate} |
44 |
|
|
|
45 |
|
|
|
46 |
|
|
This chapter deals with the mathematical basis for four |
47 |
|
|
questions. |
48 |
|
|
|
49 |
|
|
\begin{enumerate} |
50 |
|
|
\item What is the mathematical basis for redundancy to allow error |
51 |
|
|
detection and error correction? |
52 |
|
|
\item How can redundancy be added to data to enable detection of errors? |
53 |
|
|
\item How can redundancy be added to data to enable correction of |
54 |
|
|
errors? |
55 |
|
|
\item How can adding redundancy (encoding) and detecting and correcting |
56 |
|
|
errors (decoding) be performed efficiently in |
57 |
|
|
microcontroller software? |
58 |
|
|
\end{enumerate} |
59 |
|
|
|
60 |
|
|
Note that although the results presented in this chapter for the most part |
61 |
|
|
have their origins in the study of communication channels, the problem of |
62 |
|
|
protecting computer storage that may degrade (disc, tape, battery-backed RAM, |
63 |
|
|
EEPROM, etc.) is mathematically the same problem as protecting data transmitted |
64 |
|
|
through a communication channel. In either case $k$ data bits are protected |
65 |
|
|
by $n-k$ check bits (see Figure \ref{fig:cedc0:scon0:sccb0:01}), |
66 |
|
|
and the essence of the mathematical problem is how best to |
67 |
|
|
select the check bits. |
68 |
|
|
|
69 |
|
|
|
70 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
71 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
72 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
73 |
|
|
\section{Coding Concepts} |
74 |
|
|
%Section tag: con0 |
75 |
|
|
\label{cedc0:scon0} |
76 |
|
|
|
77 |
|
|
\index{coding theory}\emph{Coding theory} is the branch of mathematics |
78 |
|
|
concerned with transmitting data across noisy channels and recovering |
79 |
|
|
the data \cite{bibref:w:ctfirst50}. In this section we introduce the |
80 |
|
|
basic concepts and terminology which apply to microcontroller work. |
81 |
|
|
|
82 |
|
|
|
83 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
84 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
85 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
86 |
|
|
\subsection{Bits, Communication Channels, Messages, And Check Bits} |
87 |
|
|
%Subection tag: ccb0 |
88 |
|
|
\label{cedc0:scon0:sccb0} |
89 |
|
|
|
90 |
|
|
We assume that the data we wish to transmit is an ordered sequence of \index{bit}bits. |
91 |
|
|
Each bit is a symbol of the \index{binary alphabet}binary alphabet, |
92 |
|
|
$\mathbb{B} = \{0,1\}$. Many results in coding theory have been generalized to |
93 |
|
|
alphabets with more than two symbols, but for microcontroller work it is adequate |
94 |
|
|
to consider only $\mathbb{B}$, and in this chapter only |
95 |
|
|
$\mathbb{B}$ is considered. |
96 |
|
|
|
97 |
|
|
Bits are transmitted through a \index{communication channel}\index{channel}% |
98 |
|
|
\emph{communication channel} (or simply \emph{channel}), which may with probability $p$ |
99 |
|
|
corrupt a transmitted bit from 0 to 1 or vice-versa; or with |
100 |
|
|
probability $q=1-p$ fail to corrupt a bit. For analysis, |
101 |
|
|
we make the simplest mathematical assumptions and assume that |
102 |
|
|
the probability of corruption from 0 to 1 is the same as the probability |
103 |
|
|
of corruption from 1 to 0 (i.e. $p_{0\rightarrow{}1} = p_{1\rightarrow{}0} = p$), |
104 |
|
|
and that corruption of each bit is independent. Alternately, we may imagine that rather |
105 |
|
|
than being potentially corrupted during transmission, each bit is potentially |
106 |
|
|
corrupted by the degradation of computer storage. |
107 |
|
|
|
108 |
|
|
We assume that data is transmitted in blocks of |
109 |
|
|
$n$ bits, consisting of $k$ data bits with $n-k$ check bits |
110 |
|
|
(redundancy bits) appended (Figure \ref{fig:cedc0:scon0:sccb0:01}). This concatenation of |
111 |
|
|
$k$ data bits and $n-k$ check bits is called a \index{message}\emph{message}. |
112 |
|
|
Most commonly |
113 |
|
|
in practice, $8 \vworkdivides n,k$ (and consequently |
114 |
|
|
$8 \vworkdivides (n-k)$), although this is not required. |
115 |
|
|
If data is stored rather than transmitted, we may assume that |
116 |
|
|
the check bits are stored at the last addresses of ROM or EEPROM. |
117 |
|
|
As explained in Section \ref{cedc0:scon0:scco0}, |
118 |
|
|
in this chapter only codes where the checkbits are appended to the unmodified |
119 |
|
|
data bits are considered. |
120 |
|
|
|
121 |
|
|
Notationally, we treat the $n$-bit message as an ordered collection of |
122 |
|
|
bits, represented by a row vector |
123 |
|
|
|
124 |
|
|
\begin{equation} |
125 |
|
|
\label{eq:cedc0:scon0:sccb0:01} |
126 |
|
|
[m_0, m_1, \ldots{}, m_{n-1}] . |
127 |
|
|
\end{equation} |
128 |
|
|
|
129 |
|
|
\noindent{}(Figure \ref{fig:cedc0:scon0:sccb0:01}, |
130 |
|
|
includes bit notational conventions.) $m_0$ through $m_{k-1}$ are data bits, and |
131 |
|
|
$m_k$ through $m_{n-1}$ are check bits. We may also |
132 |
|
|
treat the vector in (\ref{eq:cedc0:scon0:sccb0:01}) as |
133 |
|
|
the concatenation of data bits $d_0$ through $d_{k-1}$ and |
134 |
|
|
check bits $c_0$ through $c_{n-k-1}$, in which case we use |
135 |
|
|
either of the following notations: |
136 |
|
|
|
137 |
|
|
\begin{eqnarray} |
138 |
|
|
\label{eq:cedc0:scon0:sccb0:02} |
139 |
|
|
& [d_0, d_1, \ldots{}, d_{k-1}, c_0, c_1, \ldots{}, c_{n-k-1}] , & \\ |
140 |
|
|
\label{eq:cedc0:scon0:sccb0:02b} |
141 |
|
|
& [d_0, d_1, \ldots{}, d_{k-1}] | [c_0, c_1, \ldots{}, c_{n-k-1}] . & |
142 |
|
|
\end{eqnarray} |
143 |
|
|
|
144 |
|
|
Implicit in |
145 |
|
|
this model is the assumption that a framing error (where communication hardware or |
146 |
|
|
software misidentifies a block of data in time) is much less probable than |
147 |
|
|
a collection of bit errors which overwhelm the detection/correction |
148 |
|
|
capability of the $n-k$ check bits. There are in fact some |
149 |
|
|
scenarios\footnote{One classic example is the CAN bit-stuffing vulnerability which can |
150 |
|
|
with some data patterns lower the Hamming distance of CAN to 2.} |
151 |
|
|
where mechanisms exist to circumvent the function of the check bits by creating |
152 |
|
|
framing errors. |
153 |
|
|
By their nature, such scenarios involve the corruption of a small number of bits |
154 |
|
|
(or samples) in a way so as to generate a framing error and shift a large number of bits |
155 |
|
|
right or left. We assume for analytic convenience that the probability of |
156 |
|
|
a framing error is much less than the probability of the corruption of enough bits |
157 |
|
|
to overwhelm the capability of the check bits. However, experience has shown that |
158 |
|
|
this assumption needs to be verified, as many practical communication protocols have |
159 |
|
|
framing weaknesses.\footnote{Note that the notion of a framing error does not apply |
160 |
|
|
to a medium that does not use start and end markers that might be misinterpreted. |
161 |
|
|
For example, ROM or EEPROM have no notion of a framing error.} |
162 |
|
|
|
163 |
|
|
\begin{figure} |
164 |
|
|
\centering |
165 |
|
|
\includegraphics[width=4.6in]{c_edc0/cword01.eps} |
166 |
|
|
\caption{Message Consisting Of The Concatenation Of $k$ Data Bits And $n-k$ |
167 |
|
|
Check Bits, With Bit Notational Conventions} |
168 |
|
|
\label{fig:cedc0:scon0:sccb0:01} |
169 |
|
|
\end{figure} |
170 |
|
|
|
171 |
|
|
We have referred to \emph{check bits} without describing the ways in which they |
172 |
|
|
might be calculated. We use the term \index{checksum}\emph{checksum} to refer |
173 |
|
|
to the contiguous group of $n-k$ check bits; whether or not the bits are calculated |
174 |
|
|
through summation. In general, we impose only the requirement that the $n-k$-bit |
175 |
|
|
checksum is a deterministic function of the $k$ data bits. |
176 |
|
|
|
177 |
|
|
We often refer to a message or a portion of a message as a |
178 |
|
|
\index{vector}\emph{vector}. This nomenclature is appropriate because it is |
179 |
|
|
convenient to treat a message as a row vector of bits. |
180 |
|
|
An 80-bit message might |
181 |
|
|
be viewed as a $1 \times 80$ matrix (i.e. a row vector) with each matrix element |
182 |
|
|
$\in \mathbb{B}$. We use \emph{message} and \emph{vector} somewhat interchangeably. |
183 |
|
|
|
184 |
|
|
We define the \index{weight}\emph{weight} of a message or vector as the number of |
185 |
|
|
1's in the message or vector. We denote the weight of a vector or message $v$ as |
186 |
|
|
$wt(v)$. |
187 |
|
|
|
188 |
|
|
|
189 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
190 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
191 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
192 |
|
|
\subsection[Codewords, Codes, And \protect\mbox{\protect$(n,k)$} Block Codes] |
193 |
|
|
{Codewords, Codes And \protect\mbox{\protect\boldmath$(n,k)$} Block Codes} |
194 |
|
|
%Subection tag: cco0 |
195 |
|
|
\label{cedc0:scon0:scco0} |
196 |
|
|
|
197 |
|
|
A \index{codeword}\emph{codeword} (as we define it here) is a message in which |
198 |
|
|
the $n-k$ check bits are consistent with the $k$ data bits. |
199 |
|
|
Under this definition, all codewords are messages, but not all possible messages |
200 |
|
|
are codewords. |
201 |
|
|
|
202 |
|
|
A common cognitive misconception is that it matters in transmission or |
203 |
|
|
storage whether the $k$ data bits or the $n-k$ check bits are corrupted. |
204 |
|
|
It matters not. We seek mathematical properties that apply to the messages |
205 |
|
|
and codewords, not to the $k$ data bits or $n-k$ check bits separately. |
206 |
|
|
|
207 |
|
|
In the most general terms, a \index{code}\emph{code} is \emph{any} system |
208 |
|
|
of information representation for transmission, not necessarily requiring |
209 |
|
|
transmission in fixed-length blocks. However, in this discussion, by |
210 |
|
|
\emph{code} we mean the set of all bit |
211 |
|
|
patterns with data and check bits consistent (i.e. all codewords) |
212 |
|
|
which can be transmitted over a communication channel or stored |
213 |
|
|
in computer memory. For example, |
214 |
|
|
$\{000, 011, 101, 110\}$ is a code. |
215 |
|
|
|
216 |
|
|
A code may be specified either by enumeration or by rule. For example, |
217 |
|
|
we might also specify the code of the previous paragraph as |
218 |
|
|
$\{ABC: C=A \oplus B\}$. With larger codes, enumeration is naturally not practical and |
219 |
|
|
also not necessary to study the properties of interest. |
220 |
|
|
|
221 |
|
|
An |
222 |
|
|
\index{(n,k) block code@$(n,k)$ block code}\index{n,k block code@$(n,k)$ block code}% |
223 |
|
|
$(n,k)$ \emph{block code} is a code where $n$ bits are transmitted (or stored) at a |
224 |
|
|
time, and characterized by a function which maps from $k$ data bits to $n$ bits which |
225 |
|
|
are transmitted (or stored). |
226 |
|
|
|
227 |
|
|
In a general $(n,k)$ block code, the $n$ transmitted |
228 |
|
|
bits are not required to contain or resemble the $k$ data bits; and if the $k$ data bits |
229 |
|
|
are contained they are not required to have a specific order or placement within |
230 |
|
|
the $n$ transmitted bits. Because we are interested in adding |
231 |
|
|
redundancy to ROM and in other applications |
232 |
|
|
where the stored data must be contiguous and unmodified, we confine ourselves |
233 |
|
|
to $(n,k)$ block codes as depicted in Figure |
234 |
|
|
\ref{fig:cedc0:scon0:sccb0:01}, where the $k$ data bits are contiguous, unchanged, |
235 |
|
|
in their original order, and prepended to the $n-k$ check bits. |
236 |
|
|
|
237 |
|
|
|
238 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
239 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
240 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
241 |
|
|
\subsection{Hamming Distance, Minimum Hamming Distance, And Errors} |
242 |
|
|
%Subection tag: mhd0 |
243 |
|
|
\label{cedc0:scon0:smhd0} |
244 |
|
|
|
245 |
|
|
We define the \index{Hamming distance}\emph{Hamming distance} between |
246 |
|
|
two same-length blocks $c$ and $d$, denoted $d(c,d)$, as the number of bit positions |
247 |
|
|
in which the blocks differ. Note that $d(c,d)$ is necessarily the same as the number |
248 |
|
|
of 1's in $c \oplus d$. Note also that $d(c,d)$ is the weight of the |
249 |
|
|
exclusive-OR of $c$ and $d$, i.e. $d(c,d) = wt(c \oplus d)$. (We discuss the properties |
250 |
|
|
of the exclusive-OR function later in Section \ref{cedc0:sfft0:dff0}.) |
251 |
|
|
|
252 |
|
|
We define the \index{minimum Hamming distance}\emph{minimum Hamming distance} |
253 |
|
|
of a code, denoted $\hat{d}$, as the smallest Hamming distance between any two |
254 |
|
|
members of the code. For example, the minimum Hamming distance of |
255 |
|
|
$\{000, 011, 101, 110\}$, |
256 |
|
|
denoted $\hat{d}(\{000, 011, 101, 110\})$, |
257 |
|
|
is 2, and the minimum Hamming distance of |
258 |
|
|
$\{0001, 0110, 1010, 1101\}$, |
259 |
|
|
denoted $\hat{d}(\{0001, 0110, 1010, 1101\})$, |
260 |
|
|
is also 2.\footnote{See Exercise |
261 |
|
|
\ref{exe:cedc0:sexe0:01}.} |
262 |
|
|
|
263 |
|
|
We define an \index{error}\emph{error} (or alternatively, a |
264 |
|
|
\emph{bit corruption} or simply a \emph{corruption}) as the corruption |
265 |
|
|
of a transmitted or stored |
266 |
|
|
bit from 0 to 1 or from 1 to 0. As mentioned in |
267 |
|
|
Section \ref{cedc0:scon0:sccb0}, we assume that a corruption may occur |
268 |
|
|
with probability $p$ or fail to occur with probability $q=1-p$. |
269 |
|
|
|
270 |
|
|
We define a \index{message corruption}\emph{message corruption} or simply |
271 |
|
|
\emph{corruption} as the corruption of one or more bits within the message |
272 |
|
|
during transmission or storage. |
273 |
|
|
Note that the minimum Hamming distance $\hat{d}$ of a code |
274 |
|
|
guarantees that at least $\hat{d}$ errors are required to transform |
275 |
|
|
one codeword into another, thus guaranteeing that any corruption |
276 |
|
|
of $\hat{d}-1$ or fewer bits is detectable. |
277 |
|
|
|
278 |
|
|
If the errors within a message are distributed in a special way, we may be |
279 |
|
|
able to devise codes that are more resistant to these special distributions |
280 |
|
|
than to an arbitrary distribution of errors. One such special distribution |
281 |
|
|
is a \index{burst error}\emph{burst error}. A \emph{burst error of length $b$} |
282 |
|
|
is defined as any number of errors in a span of $b$ bits. For example, corruption of |
283 |
|
|
00001111 to 00011001 represents a burst error of length 4 (the corruptions are in |
284 |
|
|
the 4th, 6th, and 7th bits, which span 4 bits inclusive). A burst error may naturally |
285 |
|
|
span no fewer than 1 bit and no more than $n$ bits. |
286 |
|
|
|
287 |
|
|
We are very careful \emph{not} to define a codeword as an |
288 |
|
|
uncorrupted message. No code except a code consisting of only one codeword |
289 |
|
|
can sustain an unlimited number of bit corruptions while still guaranteeing |
290 |
|
|
that the message corruption will be detectable.\footnote{This observation that |
291 |
|
|
a single-codeword code can sustain an unlimited number of bit corruptions is a |
292 |
|
|
mathematical fallacy and a semantic parlor trick. An $(n,k)$ block code with only |
293 |
|
|
one code word effectively has a maximum Hamming distance $\hat{d}$ of $n$ plus the number |
294 |
|
|
of framing bits, stop bits, etc. in the message as transmitted. Sufficient noise |
295 |
|
|
in a communication channel may cause communication hardware to believe the |
296 |
|
|
codeword was transmitted when in fact it was not. See the remarks regarding |
297 |
|
|
framing weaknesses in Section \ref{cedc0:scon0:sccb0}.} A codeword may in fact |
298 |
|
|
be a corrupted message where the number of bit corruptions has overwhelmed the |
299 |
|
|
minimum Hamming distance $\hat{d}$ of the code so as to transform one codeword |
300 |
|
|
into another. |
301 |
|
|
|
302 |
|
|
Generally, error-detecting and error-correcting codes |
303 |
|
|
(Section \ref{cedc0:scon0:secv0}) must be selected with some knowledge |
304 |
|
|
of the error |
305 |
|
|
rates of the |
306 |
|
|
communication channel or storage medium. Noisier communication channels |
307 |
|
|
or poorer storage mediums require codes with |
308 |
|
|
better error-detecting and/or error-correcting properties. Normally, the design goal |
309 |
|
|
is to achieve a very low probability of undetected corruption or uncorrectable corruption. |
310 |
|
|
|
311 |
|
|
|
312 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
313 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
314 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
315 |
|
|
\subsection{Error-Detecting Versus Error-Correcting Codes} |
316 |
|
|
%Subection tag: ecv0 |
317 |
|
|
\label{cedc0:scon0:secv0} |
318 |
|
|
|
319 |
|
|
An \index{error-detecting code}\emph{error-detecting code} is a code which is |
320 |
|
|
designed so that message errors |
321 |
|
|
(a message which is not a codeword) will be detected but not corrected. |
322 |
|
|
Error-detecting codes are attractive |
323 |
|
|
when there is the opportunity to request that the transmitter retransmit the |
324 |
|
|
corrupted data, or when obtaining a correct copy of the data is not important but |
325 |
|
|
detecting (and perhaps discarding) corrupted data is important. |
326 |
|
|
|
327 |
|
|
An \index{error-correcting code}\emph{error-correcting code} is a code designed |
328 |
|
|
so that message errors can be both detected and corrected. Error-correcting |
329 |
|
|
codes are attractive when |
330 |
|
|
there is no opportunity for retransmission of the corrupted data, but possessing |
331 |
|
|
a correct copy of the data is important. Example attractive |
332 |
|
|
applications of error-correcting codes are compact disc audio data (where the |
333 |
|
|
CD should play even with scratches, and there is no opportunity to obtain |
334 |
|
|
retransmission of the data) and data transmitted from space exploration satellites |
335 |
|
|
(where the signal-to-noise ratio is low, and there is not opportunity for retransmission |
336 |
|
|
or perhaps not even two-way communication). |
337 |
|
|
|
338 |
|
|
In this section we show the required relationship between minimum Hamming |
339 |
|
|
distance $\hat{d}$ and the error-detecting and error-correcting capabilities |
340 |
|
|
of a code. |
341 |
|
|
|
342 |
|
|
We define the \index{error-detecting capability of a code}\index{code!error-detecting capability}% |
343 |
|
|
\emph{error-detecting capability} $d_{ED}$ of a code as the largest number of bit errors |
344 |
|
|
in a message which will \emph{always} be detectable. It follows |
345 |
|
|
immediately and intuitively that |
346 |
|
|
|
347 |
|
|
\begin{equation} |
348 |
|
|
\label{eq:cedc0:scon0:secv0:01} |
349 |
|
|
d_{ED} = \hat{d} - 1 . |
350 |
|
|
\end{equation} |
351 |
|
|
|
352 |
|
|
\noindent{}If the minimum |
353 |
|
|
Hamming distance of a code is $\hat{d}$, then there exists at least |
354 |
|
|
one pair of codewords |
355 |
|
|
$c_1, c_2$ such that $d(c_1, c_2) = \hat{d}$. Thus it is possible to corrupt |
356 |
|
|
$c_1$ into $c_2$ with $\hat{d}$ corrupted bits and therefore |
357 |
|
|
$d_{ED} < \hat{d}$. On the other hand, the minimum Hamming distance |
358 |
|
|
$\hat{d}$ guarantees that it is \emph{not} possible to corrupt from one codeword to another |
359 |
|
|
with only $\hat{d}-1$ bit corruptions. Therefore |
360 |
|
|
(\ref{eq:cedc0:scon0:secv0:01}) is true. |
361 |
|
|
|
362 |
|
|
We define the \index{error correcting capability of a code}\index{code!error correcting capability}% |
363 |
|
|
\emph{error correcting capability} $d_{EC}$ of a code as the largest number of bit errors |
364 |
|
|
in a message which will \emph{always} be correctable. By \emph{correctable} we mean |
365 |
|
|
that we can recover the original $n$-bit codeword into which errors were introduced. |
366 |
|
|
|
367 |
|
|
To illustrate the relationship between Hamming distance and the error correcting |
368 |
|
|
capability of a code, consider the code $\{000, 111\}$ depicted in |
369 |
|
|
Figure \ref{fig:cedc0:scon0:secv0:01}. In the figure, each edge in the cube depicts |
370 |
|
|
a single bit error which may occur in a message. Each vertex in the cube |
371 |
|
|
represents a message. |
372 |
|
|
|
373 |
|
|
\begin{figure} |
374 |
|
|
\centering |
375 |
|
|
\includegraphics[height=2.5in]{c_edc0/cube01.eps} |
376 |
|
|
\caption{Three-Dimensional Cube Illustrating Error Correction With Code $\{000, 111\}$} |
377 |
|
|
\label{fig:cedc0:scon0:secv0:01} |
378 |
|
|
\end{figure} |
379 |
|
|
|
380 |
|
|
Note that the minimum Hamming $\hat{d}$ distance of the code $\{000, 111\}$ is 3: in |
381 |
|
|
Figure \ref{fig:cedc0:scon0:secv0:01} one must travel along three edges |
382 |
|
|
(corresponding to three bit errors) in order to travel from 000 to 111 or back. |
383 |
|
|
|
384 |
|
|
If we claim that a code has an error correcting capability of $d_{EC}$, |
385 |
|
|
then any corruption of a codeword by $d_{EC}$ errors must be correctable. |
386 |
|
|
To be \emph{correctable} means that if we guess based on the corrupted |
387 |
|
|
codeword what the original codeword is, we must always be able to guess |
388 |
|
|
correctly. This notion implies that the original codeword must be the |
389 |
|
|
closest codeword (as measured by number of bit corruptions) to the corrupted codeword. |
390 |
|
|
|
391 |
|
|
This notion of \emph{closest} codeword leads to the notion of a \emph{packing sphere}. |
392 |
|
|
A \emph{packing sphere of radius $\rho$} is the set of all messages |
393 |
|
|
at a distance of $\rho$ or less from a given codeword. In order for |
394 |
|
|
a code to have an error correcting capability of $d_{EC}=\rho$, |
395 |
|
|
the packing spheres or radius $\rho$ about all codewords must be disjoint. |
396 |
|
|
This ensures that any message at a distance $d_{EC}$ or less from a codeword |
397 |
|
|
does, in fact, have a \emph{nearest} codeword. |
398 |
|
|
|
399 |
|
|
Figure \ref{fig:cedc0:scon0:secv0:02} is |
400 |
|
|
Figure \ref{fig:cedc0:scon0:secv0:01} redrawn to show the packing spheres of |
401 |
|
|
radius $\rho=1$ about the two codewords 000 and 111. The code |
402 |
|
|
$\{000,111\}$ depicted in Figures \ref{fig:cedc0:scon0:secv0:01} and |
403 |
|
|
\ref{fig:cedc0:scon0:secv0:02} has an error correcting capability of |
404 |
|
|
$d_{EC}=1$. For error correction, any message in the packing sphere |
405 |
|
|
about 000 must be mapped back to 000, and any message in the packing sphere |
406 |
|
|
about 111 must be transformed back to 111. |
407 |
|
|
|
408 |
|
|
\begin{figure} |
409 |
|
|
\centering |
410 |
|
|
\includegraphics[height=2.5in]{c_edc0/cube02.eps} |
411 |
|
|
\caption{Packing Spheres Of Radius $\rho{}=1$ About Codewords 000 And 111} |
412 |
|
|
\label{fig:cedc0:scon0:secv0:02} |
413 |
|
|
\end{figure} |
414 |
|
|
|
415 |
|
|
The requirement for disjointness of packing spheres immediately leads to |
416 |
|
|
the constraint |
417 |
|
|
|
418 |
|
|
\begin{equation} |
419 |
|
|
\label{eq:cedc0:scon0:secv0:02} |
420 |
|
|
\hat{d} > 2 \rho |
421 |
|
|
\end{equation} |
422 |
|
|
|
423 |
|
|
\noindent{}or equivalently when considering only integers that |
424 |
|
|
|
425 |
|
|
\begin{equation} |
426 |
|
|
\label{eq:cedc0:scon0:secv0:03} |
427 |
|
|
\hat{d} \geq 2 \rho + 1 . |
428 |
|
|
\end{equation} |
429 |
|
|
|
430 |
|
|
\noindent{}Since the radius $\rho$ of the packing sphere is |
431 |
|
|
equivalent to the error correcting capability $d_{EC}$ of |
432 |
|
|
a code, we may equivalently write |
433 |
|
|
(\ref{eq:cedc0:scon0:secv0:02}) and (\ref{eq:cedc0:scon0:secv0:03}) |
434 |
|
|
as $\hat{d} > 2 d_{EC}$ and $\hat{d} \geq 2 d_{EC} + 1$, respectively. |
435 |
|
|
|
436 |
|
|
(\ref{eq:cedc0:scon0:secv0:02}) and (\ref{eq:cedc0:scon0:secv0:03}) |
437 |
|
|
treat minimum Hamming distance $\hat{d}$ as a function of |
438 |
|
|
the packing sphere radius $\rho$. With a known minimum Hamming distance |
439 |
|
|
$\hat{d}$, one may also calculate the largest disjoint |
440 |
|
|
packing spheres that can be constructed: |
441 |
|
|
|
442 |
|
|
\begin{equation} |
443 |
|
|
\label{eq:cedc0:scon0:secv0:04} |
444 |
|
|
d_{EC} = \rho = \left\lfloor {\frac{\hat{d}-1}{2}} \right\rfloor . |
445 |
|
|
\end{equation} |
446 |
|
|
|
447 |
|
|
This section has demonstrated the relationship between the minimum Hamming |
448 |
|
|
distance $\hat{d}$ of a code and the error detection capability of the code |
449 |
|
|
(Equation \ref{eq:cedc0:scon0:secv0:01}), as well as the relationship between the |
450 |
|
|
minimum Hamming |
451 |
|
|
distance $\hat{d}$ and the error correction capabilility |
452 |
|
|
(Equations \ref{eq:cedc0:scon0:secv0:02} through |
453 |
|
|
\ref{eq:cedc0:scon0:secv0:04}). |
454 |
|
|
|
455 |
|
|
Note that the relationships derived do apply to the example presented in |
456 |
|
|
Figures \ref{fig:cedc0:scon0:secv0:01} and \ref{fig:cedc0:scon0:secv0:02}. |
457 |
|
|
The code shown in the figures has a minimum Hamming distance $\hat{d}=3$. |
458 |
|
|
(\ref{eq:cedc0:scon0:secv0:01}) predicts that this code should have |
459 |
|
|
an error detection capability of $d_{ED}=2$, which is the case. |
460 |
|
|
(\ref{eq:cedc0:scon0:secv0:04}) predicts that this code should have an error correction |
461 |
|
|
capability $d_{EC}=1$, which is also the case and can be verified by |
462 |
|
|
examining Figure \ref{fig:cedc0:scon0:secv0:02}. |
463 |
|
|
|
464 |
|
|
In the code presented in Figures \ref{fig:cedc0:scon0:secv0:01} and |
465 |
|
|
\ref{fig:cedc0:scon0:secv0:02}, the union of all packing spheres of radius |
466 |
|
|
$\rho=1$ contains all messages (i.e. there are no messages which are not part of |
467 |
|
|
a packing sphere). Such a code is called a \emph{perfect code}. Most codes |
468 |
|
|
are not perfect codes, and this will be discussed later. |
469 |
|
|
|
470 |
|
|
|
471 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
472 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
473 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
474 |
|
|
\section[Finite Field Theory Applied To \protect\mbox{\protect$\mathbb{B}$}] |
475 |
|
|
{Finite Field Theory Applied To \protect\mbox{\protect\boldmath$\mathbb{B}$}} |
476 |
|
|
%Section tag: fft0 |
477 |
|
|
\label{cedc0:sfft0} |
478 |
|
|
|
479 |
|
|
This |
480 |
|
|
section deals with \index{finite field}finite field |
481 |
|
|
theory as applied to the binary alphabet, |
482 |
|
|
$\mathbb{B} = \{ 0, 1 \}$. |
483 |
|
|
This section is one of two sections in this chapter which deal with |
484 |
|
|
\index{finite field}finite field theory |
485 |
|
|
(the other section is Section \ref{cedc0:sfft1}, |
486 |
|
|
which deals with finite field theory as applied to polynomials). |
487 |
|
|
|
488 |
|
|
|
489 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
490 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
491 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
492 |
|
|
\subsection{\emph{Why} Field Theory?} |
493 |
|
|
%Subection tag: wft0 |
494 |
|
|
\label{cedc0:sfft0:wft0} |
495 |
|
|
|
496 |
|
|
The most important question to answer immediately (for engineers, anyway) |
497 |
|
|
is \emph{why} field theory is necessary at all. The answer is that |
498 |
|
|
there are two general approaches that can be used to approach coding |
499 |
|
|
theory: |
500 |
|
|
|
501 |
|
|
\begin{enumerate} |
502 |
|
|
\item \emph{Combinational:} |
503 |
|
|
approaching the problem by considering combinations and |
504 |
|
|
permutations (see Section \ref{cedc0:scob0}, for example). This approach |
505 |
|
|
can give some insight and produce useful bounds, but in general it is hard |
506 |
|
|
to approach the problem of generating codes with an arbitrarily large minimum |
507 |
|
|
Hamming distance $\hat{d}$ using a purely combinational approach. |
508 |
|
|
\item \emph{Field Theory:} approaching the problem by attempting to add algebraic |
509 |
|
|
structure to codes. This approach leads to classes of solutions that |
510 |
|
|
are unavailable using purely combinational approaches. To add |
511 |
|
|
\emph{algebraic structure} means to define operations so as to add useful |
512 |
|
|
algebraic properties that facilitate higher-level inferences |
513 |
|
|
and abstractions. For example, |
514 |
|
|
algebraic structure is ultimately what allows us to define the rank |
515 |
|
|
of a matrix with elements $\in \mathbb{B}$ in the same way we do with |
516 |
|
|
matrices with elements $\in \vworkrealset$. |
517 |
|
|
\end{enumerate} |
518 |
|
|
|
519 |
|
|
Note that combinational and field theory approaches are complementary: each |
520 |
|
|
approach gives some unique insight and solutions that the other approach cannot |
521 |
|
|
provide. |
522 |
|
|
|
523 |
|
|
Field theory is necessary in order to derive a framework in which to |
524 |
|
|
systematically generate codes with a large minimum Hamming distance $\hat{d}$. |
525 |
|
|
|
526 |
|
|
|
527 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
528 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
529 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
530 |
|
|
\subsection{Definition Of A Finite Field} |
531 |
|
|
%Subection tag: dff0 |
532 |
|
|
\label{cedc0:sfft0:dff0} |
533 |
|
|
|
534 |
|
|
We first define what a \index{finite field} \emph{finite field} is in general, and |
535 |
|
|
then we show how this definition is applied to $\mathbb{B} = \{ 0, 1 \}$. |
536 |
|
|
|
537 |
|
|
\begin{vworkdefinitionstatementpar}{Finite Field} |
538 |
|
|
A \emph{finite field} \cite{bibref:w:weissteinmathworld} |
539 |
|
|
is a finite set of elements (the cardinality of this |
540 |
|
|
set is called the \index{field order}\emph{field order}) which |
541 |
|
|
satisfies the field axioms |
542 |
|
|
listed in Table \ref{tbl:cedc0:sfft0:dff0:01} for both addition and |
543 |
|
|
multiplication. |
544 |
|
|
|
545 |
|
|
\begin{table} |
546 |
|
|
\caption{Field Axioms For A Finite Field (From \cite{bibref:w:weissteinmathworld})} |
547 |
|
|
\label{tbl:cedc0:sfft0:dff0:01} |
548 |
|
|
\begin{center} |
549 |
|
|
\begin{tabular}{|l|c|c|} |
550 |
|
|
\hline |
551 |
|
|
Name & Addition & Multiplication \\ |
552 |
|
|
\hline |
553 |
|
|
\hline |
554 |
|
|
Commutativity & $a+b = b+a$ & $ab = ba$ \\ |
555 |
|
|
\hline |
556 |
|
|
Associativity & $(a+b)+c=a+(b+c)$ & $(ab)c=a(bc)$ \\ |
557 |
|
|
\hline |
558 |
|
|
Distributivity & $a(b+c)=ab+ac$ & $(a+b)c=ac+bc$ \\ |
559 |
|
|
\hline |
560 |
|
|
Identity & $a+0=a=0+a$ & $a \cdot 1=a=1 \cdot a$ \\ |
561 |
|
|
\hline |
562 |
|
|
Inverses & $a+(-a)=0=(-a)+a$ & $aa^{-1}=1=a^{-1}a$ if $a \neq 0$ \\ |
563 |
|
|
\hline |
564 |
|
|
\end{tabular} |
565 |
|
|
\end{center} |
566 |
|
|
\end{table} |
567 |
|
|
|
568 |
|
|
Such a field is also called a \index{Galois field}\emph{Galois field}. |
569 |
|
|
In this chapter, we are concerned with the Galois field containing |
570 |
|
|
only two elements ($\mathbb{B}=\{ 0,1 \}$), and this field is denoted $GF(2)$. |
571 |
|
|
\end{vworkdefinitionstatementpar} |
572 |
|
|
\vworkdefinitionfooter{} |
573 |
|
|
|
574 |
|
|
The study of fields is a topic from \index{abstract algebra}\emph{abstract algebra}, |
575 |
|
|
a branch of mathematics. This chapter provides only the |
576 |
|
|
minimum amount of information about finite field theory to explain |
577 |
|
|
the presented application, and so there are many mathematical results |
578 |
|
|
not discussed. |
579 |
|
|
|
580 |
|
|
The definition of a finite field (Definition \ref{tbl:cedc0:sfft0:dff0:01}) |
581 |
|
|
does not specify how addition and multiplication are defined---it only |
582 |
|
|
specifies what properties must be met by whatever choice is made. |
583 |
|
|
We now present the only possible choices for addition, multiplication, |
584 |
|
|
formation of the additive inverse, and formation of the multiplicative inverse |
585 |
|
|
for the elements of $\mathbb{B}=\{ 0,1 \}$. |
586 |
|
|
|
587 |
|
|
Addition (Table \ref{tbl:cedc0:sfft0:dff0:02}) is performed modulo 2, and is |
588 |
|
|
identical to the exclusive-OR |
589 |
|
|
function. In computer software, this function is normally implemented using |
590 |
|
|
the XOR machine instruction, which operates on many bits in parallel. Although |
591 |
|
|
we would be justified in using `$+$' to denote this operation, instead we |
592 |
|
|
use `$\oplus$' because it corresponds more closely to the machine instruction |
593 |
|
|
actually used to implement this binary operation. |
594 |
|
|
|
595 |
|
|
\begin{table} |
596 |
|
|
\caption{Truth Table Of Addition Over $\mathbb{B}=\{ 0,1 \}$ (Denoted $\oplus$)} |
597 |
|
|
\label{tbl:cedc0:sfft0:dff0:02} |
598 |
|
|
\begin{center} |
599 |
|
|
\begin{tabular}{|c|c|c|} |
600 |
|
|
\hline |
601 |
|
|
$a$ & $b$ & $c = a \oplus b$ \\ |
602 |
|
|
\hline |
603 |
|
|
\hline |
604 |
|
|
0 & 0 & 0 \\ |
605 |
|
|
\hline |
606 |
|
|
0 & 1 & 1 \\ |
607 |
|
|
\hline |
608 |
|
|
1 & 0 & 1 \\ |
609 |
|
|
\hline |
610 |
|
|
1 & 1 & 0 \\ |
611 |
|
|
\hline |
612 |
|
|
\end{tabular} |
613 |
|
|
\end{center} |
614 |
|
|
\end{table} |
615 |
|
|
|
616 |
|
|
Subtraction is equivalent to adding the additive inverse. |
617 |
|
|
Table \ref{tbl:cedc0:sfft0:dff0:03} provides the |
618 |
|
|
additive inverses of the field elements 0 and 1. Table |
619 |
|
|
\ref{tbl:cedc0:sfft0:dff0:04} is the truth table for subtraction. |
620 |
|
|
|
621 |
|
|
\begin{table} |
622 |
|
|
\caption{Truth Table Of Additive Inverse Over $\mathbb{B}=\{ 0,1 \}$} |
623 |
|
|
\label{tbl:cedc0:sfft0:dff0:03} |
624 |
|
|
\begin{center} |
625 |
|
|
\begin{tabular}{|c|c|} |
626 |
|
|
\hline |
627 |
|
|
$a$ & $-a$ \\ |
628 |
|
|
\hline |
629 |
|
|
\hline |
630 |
|
|
0 & 0 \\ |
631 |
|
|
\hline |
632 |
|
|
1 & 1 \\ |
633 |
|
|
\hline |
634 |
|
|
\end{tabular} |
635 |
|
|
\end{center} |
636 |
|
|
\end{table} |
637 |
|
|
|
638 |
|
|
\begin{table} |
639 |
|
|
\caption{Truth Table Of Subtraction Over $\mathbb{B}=\{ 0,1 \}$ (Denoted $-$)} |
640 |
|
|
\label{tbl:cedc0:sfft0:dff0:04} |
641 |
|
|
\begin{center} |
642 |
|
|
\begin{tabular}{|c|c|c|} |
643 |
|
|
\hline |
644 |
|
|
$a$ & $b$ & $c = a - b = a + (-b)$ \\ |
645 |
|
|
\hline |
646 |
|
|
\hline |
647 |
|
|
0 & 0 & 0 \\ |
648 |
|
|
\hline |
649 |
|
|
0 & 1 & 1 \\ |
650 |
|
|
\hline |
651 |
|
|
1 & 0 & 1 \\ |
652 |
|
|
\hline |
653 |
|
|
1 & 1 & 0 \\ |
654 |
|
|
\hline |
655 |
|
|
\end{tabular} |
656 |
|
|
\end{center} |
657 |
|
|
\end{table} |
658 |
|
|
|
659 |
|
|
|
660 |
|
|
Table \ref{tbl:cedc0:sfft0:dff0:05} supplies the definition of the |
661 |
|
|
multiplication operation in $GF(2)$. |
662 |
|
|
|
663 |
|
|
\begin{table} |
664 |
|
|
\caption{Truth Table Of Multiplication Over $\mathbb{B}=\{ 0,1 \}$} |
665 |
|
|
\label{tbl:cedc0:sfft0:dff0:05} |
666 |
|
|
\begin{center} |
667 |
|
|
\begin{tabular}{|c|c|c|} |
668 |
|
|
\hline |
669 |
|
|
$a$ & $b$ & $c = a b$ \\ |
670 |
|
|
\hline |
671 |
|
|
\hline |
672 |
|
|
0 & 0 & 0 \\ |
673 |
|
|
\hline |
674 |
|
|
0 & 1 & 0 \\ |
675 |
|
|
\hline |
676 |
|
|
1 & 0 & 0 \\ |
677 |
|
|
\hline |
678 |
|
|
1 & 1 & 1 \\ |
679 |
|
|
\hline |
680 |
|
|
\end{tabular} |
681 |
|
|
\end{center} |
682 |
|
|
\end{table} |
683 |
|
|
|
684 |
|
|
Table \ref{tbl:cedc0:sfft0:dff0:06} supplies the definition of the |
685 |
|
|
multiplicative inverse over $GF(2)$. Note that division is assumed |
686 |
|
|
to be the same as multiplication by the multiplicative inverse. |
687 |
|
|
As required by the definition of a field, division by 0 is not |
688 |
|
|
defined. |
689 |
|
|
|
690 |
|
|
\begin{table} |
691 |
|
|
\caption{Truth Table Of Multiplicative Inverse Over $\mathbb{B}=\{ 0,1 \}$} |
692 |
|
|
\label{tbl:cedc0:sfft0:dff0:06} |
693 |
|
|
\begin{center} |
694 |
|
|
\begin{tabular}{|c|c|} |
695 |
|
|
\hline |
696 |
|
|
$a$ & $a^{-1}$ \\ |
697 |
|
|
\hline |
698 |
|
|
\hline |
699 |
|
|
0 & Undefined \\ |
700 |
|
|
\hline |
701 |
|
|
1 & 1 \\ |
702 |
|
|
\hline |
703 |
|
|
\end{tabular} |
704 |
|
|
\end{center} |
705 |
|
|
\end{table} |
706 |
|
|
|
707 |
|
|
There are unique properites of calculations within |
708 |
|
|
$GF(2)$. We summarize these unique properties here. |
709 |
|
|
|
710 |
|
|
\begin{enumerate} |
711 |
|
|
\item \label{prop:enum:cedc0:sfft0:dff0:01:01} |
712 |
|
|
Addition and subtraction |
713 |
|
|
are identical. This means that we can always replace `$-$' with `$\oplus$', |
714 |
|
|
and it also means we can break the usual rules of algebra and simply |
715 |
|
|
``drag'' terms joined by `$\oplus$' from one side of an equality to the other. |
716 |
|
|
Specifically, |
717 |
|
|
|
718 |
|
|
\begin{equation} |
719 |
|
|
\label{eq:cedc0:sfft0:dff0:01} |
720 |
|
|
(a = b \oplus c) \vworkequiv (a \oplus b = c) \vworkequiv (a \oplus b \oplus c = 0) . |
721 |
|
|
\end{equation} |
722 |
|
|
|
723 |
|
|
\item \label{prop:enum:cedc0:sfft0:dff0:01:02} |
724 |
|
|
Adding any value to itself |
725 |
|
|
yields $0$. This comes directly because $0 \oplus 0 = 1 \oplus 1=0$. |
726 |
|
|
This allows the removal of pairs of identical values joined by |
727 |
|
|
$\oplus$, i.e. |
728 |
|
|
|
729 |
|
|
\begin{equation} |
730 |
|
|
\label{eq:cedc0:sfft0:dff0:02} |
731 |
|
|
1 \oplus 1 \oplus a \oplus b \oplus a \oplus b \oplus a \oplus b \oplus a = b. |
732 |
|
|
\end{equation} |
733 |
|
|
\end{enumerate} |
734 |
|
|
|
735 |
|
|
|
736 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
737 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
738 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
739 |
|
|
\subsection[Properties Of Matrices Consisting Of Elements \mbox{\protect$\in \mathbb{B}$}] |
740 |
|
|
{Properties Of Matrices Consisting Of Elements \mbox{\protect\boldmath$\in \mathbb{B}$}} |
741 |
|
|
%Subection tag: rmc0 |
742 |
|
|
\label{cedc0:sfft0:rmc0} |
743 |
|
|
|
744 |
|
|
In high school and college, most engineers studied linear algebra using |
745 |
|
|
matrices with elements $\in \vworkrealset$. The set of real numbers combined |
746 |
|
|
with the traditional addition and multiplication operators is |
747 |
|
|
an \emph{infinite} field, whereas the set $\mathbb{B} = \{ 0, 1 \}$ combined |
748 |
|
|
with the addition and multiplication operators as defined in |
749 |
|
|
Section \ref{cedc0:sfft0:dff0} is a \emph{finite} field, namely |
750 |
|
|
$GF(2)$. It may not be clear to a practicing engineer whether the traditional notions |
751 |
|
|
from linear algebra apply to the finite field $GF(2)$ as |
752 |
|
|
defined here. |
753 |
|
|
|
754 |
|
|
It ends up that all of the traditional notions from linear algebra |
755 |
|
|
\emph{do} apply to finite fields and to $GF(2)$. Most undergraduate linear |
756 |
|
|
algebra texts, however, do not develop this. By |
757 |
|
|
\emph{traditional notions} we mean: |
758 |
|
|
|
759 |
|
|
\begin{itemize} |
760 |
|
|
\item The notion of the rank of a matrix. |
761 |
|
|
\item The notion of the determinant of a matrix (denoted $|A|$ or $det(A)$). |
762 |
|
|
\item The equivalence of all of the following statements: |
763 |
|
|
\begin{itemize} |
764 |
|
|
\item $|A_{n \times n}| = 0$. |
765 |
|
|
\item $A$ is not of full rank. |
766 |
|
|
\item Any linear combination of the rows or columns of $A$ can span |
767 |
|
|
only a subspace of $\mathbb{B}^n$. |
768 |
|
|
\end{itemize} |
769 |
|
|
\end{itemize} |
770 |
|
|
|
771 |
|
|
The notion of subspace, however, has a subtly different flavor with a finite |
772 |
|
|
field because such a subspace has a finite and countable number of elements. |
773 |
|
|
With that in mind, we present the following lemma. |
774 |
|
|
|
775 |
|
|
\begin{vworklemmastatement} |
776 |
|
|
\label{lem:cedc0:sfft0:rmc0:01} |
777 |
|
|
Linear combinations of the |
778 |
|
|
rows or columns from an |
779 |
|
|
$m \times n$ matrix $A$ with elements from $\mathbb{B}$ and with |
780 |
|
|
rank $r$ can span exactly $2^r$ vectors. |
781 |
|
|
\end{vworklemmastatement} |
782 |
|
|
\begin{vworklemmaproof} |
783 |
|
|
For simplicity assume a square matrix $A_{n \times n}$ with rank |
784 |
|
|
$r \leq n$ (the result applies also to non-square matrices and to |
785 |
|
|
the columns as well as the rows). |
786 |
|
|
Denote the rows of $A$ as $r_0 \ldots r_{n-1}$. |
787 |
|
|
Sort the rows of the matrix so that $r_0 \ldots{} r_{r-1}$ are linearly |
788 |
|
|
independent and rows $r_{r} \ldots{} r_{n-1}$ are each linear combinations |
789 |
|
|
of $r_0 \ldots{} r_{r-1}$. |
790 |
|
|
|
791 |
|
|
Consider the $2^n$ linear combinations of the |
792 |
|
|
$n$ rows, with each linear combination of the |
793 |
|
|
form $\alpha_0 r_0 + \alpha_1 r_1 + \ldots{} + \alpha_{n-1} r_{n-1}$, |
794 |
|
|
where $\alpha_i \in \mathbb{B}$. For those linear combinations |
795 |
|
|
where there are nonzero $\alpha_{r} \ldots{} \alpha_{n-1}$, since |
796 |
|
|
each $r_{r} \ldots{} r_{n-1}$ is a linear combination of |
797 |
|
|
$r_0 \ldots{} r_{r-1}$, a substitution can be made to express the |
798 |
|
|
linear combination as a sum of $r_0 \ldots{} r_{r-1}$ only, and then |
799 |
|
|
superfluous terms can be removed in pairs |
800 |
|
|
(Property \ref{prop:enum:cedc0:sfft0:dff0:01:02}, p. \pageref{prop:enum:cedc0:sfft0:dff0:01:02}) |
801 |
|
|
to give a linear combination of $r_0 \ldots{} r_{r-1}$ only. |
802 |
|
|
Thus, every $\alpha_0 r_0 + \alpha_1 r_1 + \ldots{} + \alpha_{n-1} r_{n-1}$ |
803 |
|
|
can be simplified to $\alpha_0 r_0 + \alpha_1 r_1 + \ldots{} + \alpha_{r-1} r_{r-1}$. |
804 |
|
|
Since no row $r_0 \ldots r_{r-1}$ is a linear combination of other rows |
805 |
|
|
$r_0 \ldots r_{r-1}$, each of the $2^r$ linear combinations |
806 |
|
|
is unique and thus all linear combinations of the rows |
807 |
|
|
sum to one of $2^r$ distinct $1 \times n$ vector values. |
808 |
|
|
\end{vworklemmaproof} |
809 |
|
|
\vworklemmafooter{} |
810 |
|
|
|
811 |
|
|
The ability to directly apply concepts from linear algebra to matrices |
812 |
|
|
with elements $\in \mathbb{B}$ is in fact the reason for employing finite field |
813 |
|
|
theory. We illustrate the applicability of standard linear algebra concepts to these |
814 |
|
|
types of matrices with the following example. |
815 |
|
|
|
816 |
|
|
\begin{vworkexamplestatement} |
817 |
|
|
\label{ex:cedc0:sfft0:rmc0:01} |
818 |
|
|
Consider the two matrices $A$ and $B$ with elements $\in \mathbb{B}$: |
819 |
|
|
|
820 |
|
|
\begin{equation} |
821 |
|
|
\label{eq:cedc0:sfft0:rmc0:01} |
822 |
|
|
A = \left[\begin{array}{ccc}1&1&0\\0&1&1\\1&0&1\end{array}\right], \;\; |
823 |
|
|
B = \left[\begin{array}{ccc}1&1&0\\0&1&1\\0&0&1\end{array}\right]. |
824 |
|
|
\end{equation} |
825 |
|
|
|
826 |
|
|
Determine the rank of $A$ and $B$ and the set of $1 \times 3$ vectors |
827 |
|
|
which is spanned by linear combination of their rows. |
828 |
|
|
\end{vworkexamplestatement} |
829 |
|
|
\begin{vworkexampleparsection}{Solution} |
830 |
|
|
Recall that for a $3 \times 3$ matrix |
831 |
|
|
$\left[\begin{array}{ccc}a&b&c\\d&e&f\\g&h&i\end{array}\right]$, |
832 |
|
|
the determinant is given by |
833 |
|
|
$a(ei-hf) - b(di-gf) + c(dh - ge)$. However, with |
834 |
|
|
elements from $GF(2)$, addition and subtraction are the same |
835 |
|
|
operation (Property \ref{prop:enum:cedc0:sfft0:dff0:01:01}, p. \pageref{prop:enum:cedc0:sfft0:dff0:01:01}), |
836 |
|
|
so we can replace `-' and '+' both with `$\oplus$' to give the |
837 |
|
|
simpler expression |
838 |
|
|
$a(ei \oplus hf) \oplus b(di \oplus gf) \oplus c(dh \oplus ge)$. The |
839 |
|
|
determinants of $A$ and $B$ are thus |
840 |
|
|
|
841 |
|
|
\begin{eqnarray} |
842 |
|
|
\nonumber |
843 |
|
|
|A| & = & 1 (1 \cdot 1 \oplus 0 \cdot 1) \oplus |
844 |
|
|
1 (0 \cdot 1 \oplus 1 \cdot 1) \oplus |
845 |
|
|
0 (0 \cdot 0 \oplus 1 \cdot 1) \\ |
846 |
|
|
\label{eq:cedc0:sfft0:rmc0:02} |
847 |
|
|
& = & 1 (1 \oplus 0) \oplus 1 (0 \oplus 1) \oplus 0 (0 \oplus 1) \\ |
848 |
|
|
\nonumber |
849 |
|
|
& = & 1 \oplus 1 \oplus 0 = 0 |
850 |
|
|
\end{eqnarray} |
851 |
|
|
|
852 |
|
|
\noindent{}and |
853 |
|
|
|
854 |
|
|
\begin{eqnarray} |
855 |
|
|
\nonumber |
856 |
|
|
|B| & = & 1 (1 \cdot 1 \oplus 0 \cdot 1) \oplus |
857 |
|
|
1 (0 \cdot 1 \oplus 0 \cdot 1) \oplus |
858 |
|
|
0 (0 \cdot 1 \oplus 0 \cdot 1) \\ |
859 |
|
|
\label{eq:cedc0:sfft0:rmc0:03} |
860 |
|
|
& = & 1 (1 \oplus 0) \oplus 1 (0 \oplus 0) \oplus 0 (0 \oplus 0) \\ |
861 |
|
|
\nonumber |
862 |
|
|
& = & 1 \oplus 0 \oplus 0 = 1 . |
863 |
|
|
\end{eqnarray} |
864 |
|
|
|
865 |
|
|
From the determinants, it follows that $B$ is of full rank ($rank(B)=3$) but $A$ is not. |
866 |
|
|
In fact, |
867 |
|
|
it can be seen on inspection of $A$ that the third row is the sum of the first |
868 |
|
|
two rows ($rank(A) = 2$). |
869 |
|
|
|
870 |
|
|
To enumerate the space spanned by the rows of $A$ and $B$, one can form the sum |
871 |
|
|
$\alpha_0 r_0 \oplus \alpha_1 r_1 \oplus \alpha_2 r_2$ and vary the parameters |
872 |
|
|
$\alpha_0, \alpha_1, \alpha_2 \in \mathbb{B}$. |
873 |
|
|
Table \ref{tbl:cedc0:sfft0:rmc0:01} supplies this range for |
874 |
|
|
$A$ and Table \ref{tbl:cedc0:sfft0:rmc0:02} supplies this range |
875 |
|
|
for $B$. |
876 |
|
|
|
877 |
|
|
\begin{table} |
878 |
|
|
\caption{Range Of $\alpha_0 r_0 \oplus \alpha_1 r_1 \oplus \alpha_2 r_2$ For $A$ Of Example \ref{ex:cedc0:sfft0:rmc0:01}} |
879 |
|
|
\label{tbl:cedc0:sfft0:rmc0:01} |
880 |
|
|
\begin{center} |
881 |
|
|
\begin{tabular}{|c|c|c|l|} |
882 |
|
|
\hline |
883 |
|
|
$\alpha_0$ & $\alpha_1$ & $\alpha_2$ & $\alpha_0 [1 \; 1 \; 0] \oplus \alpha_1 [0 \; 1 \; 1] \oplus \alpha_2 [1 \; 0 \; 1]$ \\ |
884 |
|
|
\hline |
885 |
|
|
\hline |
886 |
|
|
0 & 0 & 0 & $[0\;0\;0]$ \\ |
887 |
|
|
\hline |
888 |
|
|
0 & 0 & 1 & $[1\;0\;1]$ \\ |
889 |
|
|
\hline |
890 |
|
|
0 & 1 & 0 & $[0\;1\;1]$ \\ |
891 |
|
|
\hline |
892 |
|
|
0 & 1 & 1 & $[0\;1\;1] \oplus [1\;0\;1]$ \\ |
893 |
|
|
& & & $[0 \oplus 1 \;\; 1 \oplus 0\;\; 1 \oplus 1]$ \\ |
894 |
|
|
& & & $[1\;1\;0]$ \\ |
895 |
|
|
\hline |
896 |
|
|
1 & 0 & 0 & $[1\;1\;0]$ \\ |
897 |
|
|
\hline |
898 |
|
|
1 & 0 & 1 & $[1\;1\;0] \oplus [1\;0\;1]$ \\ |
899 |
|
|
& & & $[1 \oplus 1 \;\; 1 \oplus 0\;\; 0 \oplus 1]$ \\ |
900 |
|
|
& & & $[0\;1\;1]$ \\ |
901 |
|
|
\hline |
902 |
|
|
1 & 1 & 0 & $[1\;1\;0] \oplus [0\;1\;1]$ \\ |
903 |
|
|
& & & $[1 \oplus 0 \;\; 1 \oplus 1\;\; 0 \oplus 1]$ \\ |
904 |
|
|
& & & $[1\;0\;1]$ \\ |
905 |
|
|
\hline |
906 |
|
|
1 & 1 & 1 & $[1\;1\;0] \oplus [0\;1\;1] \oplus [1\;0\;1]$ \\ |
907 |
|
|
& & & $[1 \oplus 0 \oplus 1 \;\; 1 \oplus 1 \oplus 0\;\; 0 \oplus 1 \oplus 1]$ \\ |
908 |
|
|
& & & $[0\;0\;0]$ \\ |
909 |
|
|
\hline |
910 |
|
|
\end{tabular} |
911 |
|
|
\end{center} |
912 |
|
|
\end{table} |
913 |
|
|
|
914 |
|
|
\begin{table} |
915 |
|
|
\caption{Range Of $\alpha_0 r_0 \oplus \alpha_1 r_1 \oplus \alpha_2 r_2$ For $B$ Of Example \ref{ex:cedc0:sfft0:rmc0:01}} |
916 |
|
|
\label{tbl:cedc0:sfft0:rmc0:02} |
917 |
|
|
\begin{center} |
918 |
|
|
\begin{tabular}{|c|c|c|l|} |
919 |
|
|
\hline |
920 |
|
|
$\alpha_0$ & $\alpha_1$ & $\alpha_2$ & $\alpha_0 [1 \; 1 \; 0] \oplus \alpha_1 [0 \; 1 \; 1] \oplus \alpha_2 [0 \; 0 \; 1]$ \\ |
921 |
|
|
\hline |
922 |
|
|
\hline |
923 |
|
|
0 & 0 & 0 & $[0\;0\;0]$ \\ |
924 |
|
|
\hline |
925 |
|
|
0 & 0 & 1 & $[0\;0\;1]$ \\ |
926 |
|
|
\hline |
927 |
|
|
0 & 1 & 0 & $[0\;1\;1]$ \\ |
928 |
|
|
\hline |
929 |
|
|
0 & 1 & 1 & $[0\;1\;1] \oplus [0\;0\;1]$ \\ |
930 |
|
|
& & & $[0 \oplus 0 \;\; 1 \oplus 0\;\; 1 \oplus 1]$ \\ |
931 |
|
|
& & & $[0\;1\;0]$ \\ |
932 |
|
|
\hline |
933 |
|
|
1 & 0 & 0 & $[1\;1\;0]$ \\ |
934 |
|
|
\hline |
935 |
|
|
1 & 0 & 1 & $[1\;1\;0] \oplus [0\;0\;1]$ \\ |
936 |
|
|
& & & $[1 \oplus 0 \;\; 1 \oplus 0\;\; 0 \oplus 1]$ \\ |
937 |
|
|
& & & $[1\;1\;1]$ \\ |
938 |
|
|
\hline |
939 |
|
|
1 & 1 & 0 & $[1\;1\;0] \oplus [0\;1\;1]$ \\ |
940 |
|
|
& & & $[1 \oplus 0 \;\; 1 \oplus 1\;\; 0 \oplus 1]$ \\ |
941 |
|
|
& & & $[1\;0\;1]$ \\ |
942 |
|
|
\hline |
943 |
|
|
1 & 1 & 1 & $[1\;1\;0] \oplus [0\;1\;1] \oplus [0\;0\;1]$ \\ |
944 |
|
|
& & & $[1 \oplus 0 \oplus 0 \;\; 1 \oplus 1 \oplus 0\;\; 0 \oplus 1 \oplus 1]$ \\ |
945 |
|
|
& & & $[1\;0\;0]$ \\ |
946 |
|
|
\hline |
947 |
|
|
\end{tabular} |
948 |
|
|
\end{center} |
949 |
|
|
\end{table} |
950 |
|
|
|
951 |
|
|
Note from the tables that the rows of $A$ span 4 vectors |
952 |
|
|
(000, 011, 101, and 110), which is consistent |
953 |
|
|
by Lemma \ref{lem:cedc0:sfft0:rmc0:01} with a matrix of rank 2. |
954 |
|
|
Note also that the rows of $B$ span the full space of |
955 |
|
|
$2^3$ vectors (000, 001, 010, 011, 100, 101, 110, and 111), which |
956 |
|
|
is consistent with a full-rank matrix. |
957 |
|
|
\end{vworkexampleparsection} |
958 |
|
|
\vworkexamplefooter{} |
959 |
|
|
|
960 |
|
|
|
961 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
962 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
963 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
964 |
|
|
\section[Combinatoric Observations] |
965 |
|
|
{Combinatoric Observations About \protect\mbox{\protect\boldmath$(n,k)$} Block Codes} |
966 |
|
|
%Section tag: cob0 |
967 |
|
|
\label{cedc0:scob0} |
968 |
|
|
|
969 |
|
|
A surprising number of observations about $(n,k)$ block codes can be made by |
970 |
|
|
simply considering combinatoric aspects of the codes. In Section |
971 |
|
|
\ref{cedc0:scon0:sccb0} and Figure \ref{fig:cedc0:scon0:sccb0:01} |
972 |
|
|
(p. \pageref{fig:cedc0:scon0:sccb0:01}), no assumptions about the function which |
973 |
|
|
maps from the $k$ data bits to the $n-k$ checksum bits (other than determinism) |
974 |
|
|
were made. Even with only the assumption of determinism, a large number of properties |
975 |
|
|
can be derived or deduced, and we do this here. In the following |
976 |
|
|
subsections, it may be necessary to make slightly stronger assumptions in order |
977 |
|
|
to derive properties. |
978 |
|
|
|
979 |
|
|
|
980 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
981 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
982 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
983 |
|
|
\subsection[Packing Spheres Of Radius \protect\mbox{\protect$\rho$}] |
984 |
|
|
{Surface Area And Volume Of Packing Spheres Of Radius \protect\mbox{\protect\boldmath$\rho$}} |
985 |
|
|
%Subsection tag: psr0 |
986 |
|
|
\label{cedc0:scob0:psr0} |
987 |
|
|
|
988 |
|
|
As discussed in Section \ref{cedc0:scon0:sccb0}, we are interested in constructing |
989 |
|
|
messages consisting of $n$ symbols from the binary alphabet |
990 |
|
|
|
991 |
|
|
\begin{equation} |
992 |
|
|
\label{eq:cedc0:scob0:psr0:01} |
993 |
|
|
\mathbb{B} = \{ 0, 1 \} , |
994 |
|
|
\end{equation} |
995 |
|
|
|
996 |
|
|
\noindent{}with $k$ symbols being arbitrarily chosen (data), and the remaining |
997 |
|
|
$n-k$ symbols being check bits. |
998 |
|
|
|
999 |
|
|
As mentioned in Section \ref{cedc0:scon0:secv0}, the minimum Hamming distance |
1000 |
|
|
$\hat{d}$ |
1001 |
|
|
of a |
1002 |
|
|
code is related to its error detection capability (Eq. \ref{eq:cedc0:scon0:secv0:01}) |
1003 |
|
|
and to its error correction capability (Eq. \ref{eq:cedc0:scon0:secv0:04}). |
1004 |
|
|
It is most natural to think of the minimum Hamming distance $\hat{d}$ of a code |
1005 |
|
|
in terms of disjoint packing spheres or radius $\rho$, where $\hat{d} = 2 \rho + 1$, |
1006 |
|
|
rather than considering Hamming distance directly. In this section, we |
1007 |
|
|
derive the surface area\footnote{To use \emph{surface area} in this way is perhaps |
1008 |
|
|
a mild abuse of nomenclature.} and volume of packing spheres. |
1009 |
|
|
|
1010 |
|
|
We define the surface area of a packing sphere of radius $\rho$ to be the |
1011 |
|
|
number of messages which are exactly at Hamming distance $\rho$ from a message |
1012 |
|
|
being considered. To say that a message $c_2$ is exactly at distance |
1013 |
|
|
$\rho$ from $c_1$ is equivalent to saying that the error vector has weight $\rho$. |
1014 |
|
|
|
1015 |
|
|
Thus, for an $(n,k)$ block code, the number of messages that are precisely |
1016 |
|
|
at a distance $\rho$ from another message is given by |
1017 |
|
|
|
1018 |
|
|
\begin{equation} |
1019 |
|
|
\label{eq:cedc0:scob0:psr0:02} |
1020 |
|
|
S(n, \rho ) = \left({\begin{array}{cc}n\\\rho\end{array}}\right) . |
1021 |
|
|
\end{equation} |
1022 |
|
|
|
1023 |
|
|
\noindent{}This formula comes directly from considering the |
1024 |
|
|
number of $n$-bit error vectors of weight $\rho$ that can be constructed. |
1025 |
|
|
|
1026 |
|
|
We define the volume of a packing sphere of radius $\rho$ to be the |
1027 |
|
|
number of messages which are at a distance $\rho$ or less from a |
1028 |
|
|
message being considered. This volume can be obtained by |
1029 |
|
|
simply summing the number of messages at distances |
1030 |
|
|
$0 \leq d \leq \rho$ from the message being considered: |
1031 |
|
|
|
1032 |
|
|
\begin{eqnarray} |
1033 |
|
|
\label{eq:cedc0:scob0:psr0:03} |
1034 |
|
|
V(n, \rho ) & = & \sum_{d=0}^{\rho} \left({\begin{array}{cc}n\\d\end{array}}\right) \\ |
1035 |
|
|
\nonumber |
1036 |
|
|
& = & 1 |
1037 |
|
|
+ \left({\begin{array}{cc}n\\1\end{array}}\right) |
1038 |
|
|
+ \left({\begin{array}{cc}n\\2\end{array}}\right) |
1039 |
|
|
+ \ldots{} |
1040 |
|
|
+ \left({\begin{array}{cc}n\\\rho\end{array}}\right) |
1041 |
|
|
\end{eqnarray} |
1042 |
|
|
|
1043 |
|
|
\noindent{}Note in (\ref{eq:cedc0:scob0:psr0:03}) |
1044 |
|
|
that $d=0$ is included because the messsage being considered |
1045 |
|
|
(at distance 0) is also within the sphere. Note also that there is no |
1046 |
|
|
way to simplify the summation in (\ref{eq:cedc0:scob0:psr0:03}). |
1047 |
|
|
|
1048 |
|
|
|
1049 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1050 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1051 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1052 |
|
|
\subsection[Relationship Between Number Of Check Bits |
1053 |
|
|
\protect\mbox{\protect$n-k$} |
1054 |
|
|
And Minimum Hamming |
1055 |
|
|
Distance \protect\mbox{\protect$\hat{d}$}] |
1056 |
|
|
{Relationship Between Number Of Check Bits |
1057 |
|
|
\protect\mbox{\protect\boldmath$n-k$} |
1058 |
|
|
And Minimum Hamming |
1059 |
|
|
Distance \protect\mbox{\protect\boldmath$\hat{d}$}} |
1060 |
|
|
%Subsection tag: rbc0 |
1061 |
|
|
\label{cedc0:scob0:rbc0} |
1062 |
|
|
|
1063 |
|
|
Given that we wish to reliably transmit or store $k$ data bits, |
1064 |
|
|
we are interested in discovering how much protection (in terms of the |
1065 |
|
|
minimum Hamming distance $\hat{d}$) we can purchase with $n-k$ check bits. |
1066 |
|
|
In this section, |
1067 |
|
|
we develop |
1068 |
|
|
fundamental limiting |
1069 |
|
|
relationships between $n$, $k$, and $\hat{d}$ for $(n,k)$ block codes. |
1070 |
|
|
|
1071 |
|
|
|
1072 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1073 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1074 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1075 |
|
|
\subsubsection{Absolute Upper Limit} |
1076 |
|
|
%Subsubsection tag: aul0 |
1077 |
|
|
\label{cedc0:scob0:rbc0:saul0} |
1078 |
|
|
|
1079 |
|
|
The \index{Singleton bound}Singleton bound (Lemma \ref{lem:cedc0:slco0:spcd0:03}) |
1080 |
|
|
can also be proved combinationally using the |
1081 |
|
|
pigeonhole principle. |
1082 |
|
|
|
1083 |
|
|
It is obvious combinationally that \emph{no code can detect more than |
1084 |
|
|
$n-k$ corruptions} (this is a restatement of the Singleton bound given in |
1085 |
|
|
Lemma \ref{lem:cedc0:slco0:spcd0:03}). To understand why this must be true, |
1086 |
|
|
choose $m = n-k+1$ bits among the $k$ data bits to vary. Note that there |
1087 |
|
|
are $2^m$ patterns for the $m$ data bits, but only $2^{n-k}$ patterns for the |
1088 |
|
|
$n-k$ check bits. Thus, by the pigeonhole principle, at least one pair of patterns among the |
1089 |
|
|
data bits maps to the same pattern among the check bits. Thus, we can generate two |
1090 |
|
|
codewords having the same check bits by varying $m$ of the $k$ data bits, and thus we can |
1091 |
|
|
change one codeword to another with $n-k+1$ corruptions. |
1092 |
|
|
|
1093 |
|
|
|
1094 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1095 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1096 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1097 |
|
|
\subsubsection{Hamming (Sphere-Packing) Bound} |
1098 |
|
|
%Subsubsection tag: hsp0 |
1099 |
|
|
\label{cedc0:scob0:rbc0:shsp0} |
1100 |
|
|
|
1101 |
|
|
The most obvious bound comes about by considering that for a code with a |
1102 |
|
|
minimum Hamming distance $\hat{d}$ (assumed odd), the $2^k$ packing spheres each with |
1103 |
|
|
volume $V(n, \rho = (\hat{d}-1)/2 )$ must ``fit'' in the space |
1104 |
|
|
of $2^n$ messages that can be formed. This immediately leads to the |
1105 |
|
|
constraint |
1106 |
|
|
|
1107 |
|
|
\begin{equation} |
1108 |
|
|
\label{eq:cedc0:scob0:rbc0:shsp0:01} |
1109 |
|
|
2^k V(n, \rho) \leq 2^n . |
1110 |
|
|
\end{equation} |
1111 |
|
|
|
1112 |
|
|
\noindent{}(\ref{eq:cedc0:scob0:rbc0:shsp0:01}) states that the number of codewords |
1113 |
|
|
($2^k$ of them, one for each possible combination of the $k$ data bits) multiplied |
1114 |
|
|
by the number of messages required to populate a packing sphere around each codeword |
1115 |
|
|
adequate to guarantee |
1116 |
|
|
the minimum Hammming distance must be less than the number of message patterns |
1117 |
|
|
available ($2^n$ of them, one for each possible combination of the $n$ message bits). |
1118 |
|
|
Note that (\ref{eq:cedc0:scob0:rbc0:shsp0:01}) is a necessary condition for the existence |
1119 |
|
|
of a code with |
1120 |
|
|
a minimum Hamming distance of $\hat{d} = 2 \rho + 1$, but not a sufficient condition. |
1121 |
|
|
|
1122 |
|
|
|
1123 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1124 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1125 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1126 |
|
|
\subsection{Linear Codes} |
1127 |
|
|
%Subection tag: lco0 |
1128 |
|
|
\label{cedc0:scon0:slco0} |
1129 |
|
|
|
1130 |
|
|
|
1131 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1132 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1133 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1134 |
|
|
\subsection{Burst Errors} |
1135 |
|
|
%Subection tag: bhe0 |
1136 |
|
|
\label{cedc0:scon0:sbhe0} |
1137 |
|
|
|
1138 |
|
|
Need to define burst error capability $d_B$ as the size of the frame |
1139 |
|
|
in which unlimited errors may occur. |
1140 |
|
|
|
1141 |
|
|
|
1142 |
|
|
|
1143 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1144 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1145 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1146 |
|
|
\subsection{Metrics Of Goodness} |
1147 |
|
|
%Subection tag: mgo0 |
1148 |
|
|
\label{cedc0:scon0:smgo0} |
1149 |
|
|
|
1150 |
|
|
Given multiple possible strategies for implementing an error-detecting |
1151 |
|
|
or error-correcting code, how does one decide that one strategy is |
1152 |
|
|
better than another? What are the characteristics of merit |
1153 |
|
|
(or metrics of goodness) which should be used to rate strategies? This |
1154 |
|
|
question is especially relevant to microcontroller work, where strategies may |
1155 |
|
|
be chosen for efficiency and so may have some benefits but may not |
1156 |
|
|
have all mathematical properties normally associated with error detecting |
1157 |
|
|
and error correcting codes. |
1158 |
|
|
|
1159 |
|
|
We propose the following metrics of goodness for error detection and correction |
1160 |
|
|
strategies. |
1161 |
|
|
|
1162 |
|
|
\begin{enumerate} |
1163 |
|
|
\item \label{enum:cedc0:scon0:smgo0:01:01} |
1164 |
|
|
\textbf{Execution Time:} |
1165 |
|
|
Particularly for ROM checksum strategies that execute at product startup |
1166 |
|
|
or protect large blocks of data, execution time is critical. We |
1167 |
|
|
accept the TMS370C8 with a 12Mhz crystal as |
1168 |
|
|
a protypical inexpensive microcontroller, and |
1169 |
|
|
we express execution time as a linear model with offset. If |
1170 |
|
|
$m$ is the number of bytes to be protected (including the |
1171 |
|
|
checksum), we parameterize the performance by $t_s$ and $t_d$ so that |
1172 |
|
|
the time $t_{EX}$ to calculate the checksum is given by |
1173 |
|
|
|
1174 |
|
|
\begin{equation} |
1175 |
|
|
\label{eq:cedc0:scon0:smgo0:01} |
1176 |
|
|
t_{EX} = t_s + m t_d . |
1177 |
|
|
\end{equation} |
1178 |
|
|
|
1179 |
|
|
The parameter $t_s$ is included to properly characterize algorithms that have |
1180 |
|
|
a large setup or cleanup time. Note also that any differences between |
1181 |
|
|
algorithms in the size |
1182 |
|
|
of the checksum are accounted for by defining $m$ to include the checksum and |
1183 |
|
|
suitably adjusting $t_s$ (however, note that any such adjustments will be |
1184 |
|
|
\emph{very} small, as the checksum is typically very small in relation to the |
1185 |
|
|
data being protected). |
1186 |
|
|
|
1187 |
|
|
\item \label{enum:cedc0:scon0:smgo0:01:02} |
1188 |
|
|
\textbf{Minimum Hamming Distance \mbox{\boldmath$\hat{d}$} Of The Code:} |
1189 |
|
|
This is a very useful metric, and a larger $\hat{d}$ is better. However, |
1190 |
|
|
this metric can be misleading, and so the metric immediately below is also |
1191 |
|
|
applied. |
1192 |
|
|
|
1193 |
|
|
\item \label{enum:cedc0:scon0:smgo0:01:03} |
1194 |
|
|
\textbf{Probability Of Undetected Corruption As A Function Of \mbox{\boldmath$p$}:} |
1195 |
|
|
In microcontroller work, the minimum Hamming distance $\hat{d}$ of a |
1196 |
|
|
code may not give a complete metric for evaluation. For example, it |
1197 |
|
|
may be possible in practice to devise an efficient code such that nearly all |
1198 |
|
|
codewords are separated by a large Hamming distance but a small fraction |
1199 |
|
|
of codewords are separated by a small Hamming distance. In such a case, |
1200 |
|
|
the minimum Hamming distance $\hat{d}$ may not reflect the actual goodness |
1201 |
|
|
of the code. We are very interested in the actual probabilities of undetected |
1202 |
|
|
corruption as a function of $p$ when random bits are chosen to corrupt. |
1203 |
|
|
|
1204 |
|
|
\item \label{enum:cedc0:scon0:smgo0:01:04} |
1205 |
|
|
\textbf{Applicability Of The Code As An Error-Correcting Code:} |
1206 |
|
|
A code with a minimum Hamming distance $\hat{d}$ of at least 3 can be harnessed as |
1207 |
|
|
an error-correcting code. However, the cost of the decoding step needs to be |
1208 |
|
|
considered. Two questions are of interest: |
1209 |
|
|
|
1210 |
|
|
\begin{enumerate} |
1211 |
|
|
\item \textbf{Is a practical algorithm known for decoding (i.e. for mapping from the |
1212 |
|
|
message received to the nearest codeword)?} It may be possible to devise codes |
1213 |
|
|
with $\hat{d} \geq 3$ that are not practical to decode. |
1214 |
|
|
\item \textbf{What is the cost of this algorithm?} The cost would be parameterized |
1215 |
|
|
as in (\ref{eq:cedc0:scon0:smgo0:01}). |
1216 |
|
|
\end{enumerate} |
1217 |
|
|
\end{enumerate} |
1218 |
|
|
|
1219 |
|
|
|
1220 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1221 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1222 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1223 |
|
|
\section{Linear Codes} |
1224 |
|
|
%Section tag: lco0 |
1225 |
|
|
\label{cedc0:slco0} |
1226 |
|
|
|
1227 |
|
|
|
1228 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1229 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1230 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1231 |
|
|
\subsection{Definition} |
1232 |
|
|
\label{cedc0:slco0:sdef0} |
1233 |
|
|
|
1234 |
|
|
A linear code is simply a subspace of $\mathbb{B}^n$. In this definition, |
1235 |
|
|
by \emph{subspace} we mean subspace in the conventional linear algebra |
1236 |
|
|
sense where the subspace is spanned by linear combinations of a set of vectors, |
1237 |
|
|
and we operate within the finite field $GF(2)$ for each vector or matrix element. |
1238 |
|
|
|
1239 |
|
|
As an example of a linear code, consider the $(5,3)$ block code consisting |
1240 |
|
|
of vectors of the form $[a\;b\;c\;d\;e]$ where $d = a \oplus b$ and |
1241 |
|
|
$e = b \oplus c$. Such a code can be characterized by a generator |
1242 |
|
|
matrix |
1243 |
|
|
|
1244 |
|
|
\begin{equation} |
1245 |
|
|
\label{eq:cedc0:slco0:sdef0:01} |
1246 |
|
|
G = \left[ |
1247 |
|
|
\begin{array}{ccccc} |
1248 |
|
|
1&0&0&1&0 \\ |
1249 |
|
|
0&1&0&1&1 \\ |
1250 |
|
|
0&0&1&0&1 |
1251 |
|
|
\end{array} |
1252 |
|
|
\right] |
1253 |
|
|
\end{equation} |
1254 |
|
|
|
1255 |
|
|
\noindent{}where any codeword in the code is a linear combination of the rows |
1256 |
|
|
of $G$. |
1257 |
|
|
|
1258 |
|
|
We can calculate all of the codewords in the code defined by $G$ by |
1259 |
|
|
forming all of the linear combinations of the rows of $G$. |
1260 |
|
|
A linear combination of the rows of $G$ is of the form |
1261 |
|
|
|
1262 |
|
|
\begin{equation} |
1263 |
|
|
\label{eq:cedc0:slco0:sdef0:02} |
1264 |
|
|
\alpha_0 [1\;0\;0\;1\;0] |
1265 |
|
|
\oplus |
1266 |
|
|
\alpha_1 [0\;1\;0\;1\;1] |
1267 |
|
|
\oplus |
1268 |
|
|
\alpha_2 [0\;0\;1\;0\;1], |
1269 |
|
|
\end{equation} |
1270 |
|
|
|
1271 |
|
|
\noindent{}where $\alpha_0, \alpha_1, \alpha_2 \in \mathbb{B}$. |
1272 |
|
|
It can be verified that the codewords formed by varying |
1273 |
|
|
$\alpha_0, \alpha_1, \alpha_2$ in (\ref{eq:cedc0:slco0:sdef0:02}) |
1274 |
|
|
are 00000, 00101, 01011, 01110, 10010, 10111, 11001, and 11100. |
1275 |
|
|
|
1276 |
|
|
There are many properties of linear codes that follow immediately |
1277 |
|
|
from the definition of a linear code as a subspace. However, we |
1278 |
|
|
delay introducing these properties until Section \ref{cedc0:slco0:splc0}, |
1279 |
|
|
until after the parity check matrix (Section \ref{cedc0:slco0:spcm0}) and the |
1280 |
|
|
generator matrix (Section \ref{cedc0:slco0:sgma0}) have been introduced. |
1281 |
|
|
|
1282 |
|
|
|
1283 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1284 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1285 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1286 |
|
|
\subsection{The Parity Check Matrix} |
1287 |
|
|
\label{cedc0:slco0:spcm0} |
1288 |
|
|
|
1289 |
|
|
Any linear code can be characterized by a |
1290 |
|
|
\index{parity check matrix}\emph{parity check matrix} $H$ such that |
1291 |
|
|
for any codeword $m = [m_0, m_1, \ldots{}, m_{n-1}]$ in the |
1292 |
|
|
code, |
1293 |
|
|
|
1294 |
|
|
\begin{equation} |
1295 |
|
|
\label{eq:cedc0:slco0:spcm0:01} |
1296 |
|
|
H m^T = \mathbf{0} . |
1297 |
|
|
\end{equation} |
1298 |
|
|
|
1299 |
|
|
\noindent{}More explicitly, we may write (\ref{eq:cedc0:slco0:spcm0:01}) |
1300 |
|
|
as |
1301 |
|
|
|
1302 |
|
|
\begin{equation} |
1303 |
|
|
\label{eq:cedc0:slco0:spcm0:02} |
1304 |
|
|
\left[\begin{array}{llcl} |
1305 |
|
|
h_{0,0} & h_{0,1} & \cdots{} & h_{0,n-1} \\ |
1306 |
|
|
h_{1,0} & h_{1,1} & \cdots{} & h_{1,n-1} \\ |
1307 |
|
|
\;\;\vdots & \;\;\vdots & \ddots{} & \;\;\vdots \\ |
1308 |
|
|
h_{n-k-1,0} & h_{n-k-1,1} & \cdots{} & h_{n-k-1,n-1} \\ |
1309 |
|
|
\end{array}\right] |
1310 |
|
|
\left[\begin{array}{l}m_0\\m_1\\\;\;\vdots{}\\m_{n-1}\end{array}\right] |
1311 |
|
|
= \left[\begin{array}{c}0\\0\\\vdots{}\\0\end{array}\right] |
1312 |
|
|
\end{equation} |
1313 |
|
|
|
1314 |
|
|
\noindent{}where of course |
1315 |
|
|
|
1316 |
|
|
\begin{equation} |
1317 |
|
|
\label{eq:cedc0:slco0:spcm0:03} |
1318 |
|
|
H = \left[\begin{array}{llcl} |
1319 |
|
|
h_{0,0} & h_{0,1} & \cdots{} & h_{0,n-1} \\ |
1320 |
|
|
h_{1,0} & h_{1,1} & \cdots{} & h_{1,n-1} \\ |
1321 |
|
|
\;\;\vdots & \;\;\vdots & \ddots{} & \;\;\vdots \\ |
1322 |
|
|
h_{n-k-1,0} & h_{n-k-1,1} & \cdots{} & h_{n-k-1,n-1} \\ |
1323 |
|
|
\end{array}\right] |
1324 |
|
|
\end{equation} |
1325 |
|
|
|
1326 |
|
|
\noindent{}and |
1327 |
|
|
|
1328 |
|
|
\begin{equation} |
1329 |
|
|
\label{eq:cedc0:slco0:spcm0:04} |
1330 |
|
|
m^T = |
1331 |
|
|
\left[\begin{array}{l}m_0\\m_1\\\;\;\vdots{}\\m_{n-1}\end{array}\right] . |
1332 |
|
|
\end{equation} |
1333 |
|
|
|
1334 |
|
|
Note that $H$ has the same number of columns as message bits and |
1335 |
|
|
the same number of rows as check bits. |
1336 |
|
|
|
1337 |
|
|
Each row of $H$ specifies a required relationship between two or more |
1338 |
|
|
message bits. In the case of (\ref{eq:cedc0:slco0:spcm0:02}), these |
1339 |
|
|
$n-k$ relationships are |
1340 |
|
|
|
1341 |
|
|
\begin{eqnarray} |
1342 |
|
|
\nonumber h_{0,0} m_{0} + h_{0,1} m_{1} + \cdots{} h_{0,n-1} m_{n-1} & = & 0 \\ |
1343 |
|
|
\label{eq:cedc0:slco0:spcm0:05} |
1344 |
|
|
h_{1,0} m_{1} + h_{1,1} m_{1} + \cdots{} h_{1,n-1} m_{n-1} & = & 0 \\ |
1345 |
|
|
\nonumber & \vdots & \\ |
1346 |
|
|
\nonumber h_{n-k-1,0} m_{0} + h_{n-k-1,1} m_{1} + \cdots{} h_{n-k-1,n-1} m_{n-1} & = & 0 |
1347 |
|
|
\end{eqnarray} |
1348 |
|
|
|
1349 |
|
|
In the general case $H$ is arbitrary except that each row must |
1350 |
|
|
have at least two non-zero elements. However, because we are |
1351 |
|
|
interested only in codes where the check bits are concatenated |
1352 |
|
|
to the data bits (see Section \ref{cedc0:scon0:sccb0} and Figure |
1353 |
|
|
\ref{fig:cedc0:scon0:sccb0:01}), it is immediately |
1354 |
|
|
apparent that each row of $H$ must have at least one non-zero entry |
1355 |
|
|
in columns $n-k$ through $n-1$. If this condition were not met, $H$ would |
1356 |
|
|
specify a required |
1357 |
|
|
relationship between the $k$ data bits, which would mean that the $k$ data bits |
1358 |
|
|
could not be chosen freely. |
1359 |
|
|
|
1360 |
|
|
For the case where $n-k$ check bits are appended to $k$ data bits, we |
1361 |
|
|
seek to describe the code by a parity check matrix $H$ where the |
1362 |
|
|
rightmost $n-k$ columns are the identity matrix. If $H$ is arranged in this |
1363 |
|
|
way, each row of $H$ defines one of the $n-k$ check bits in terms of the $k$ data bits. |
1364 |
|
|
In other words, we generally seek to write $H$ as a concatenated matrix |
1365 |
|
|
|
1366 |
|
|
\begin{equation} |
1367 |
|
|
\label{eq:cedc0:slco0:spcm0:06} |
1368 |
|
|
H_{n-k \times n} = [H'_{n-k \times k} | I_{n-k \times n-k} ], |
1369 |
|
|
\end{equation} |
1370 |
|
|
|
1371 |
|
|
\noindent{}where the subscripts provide the dimensions of the matrices. |
1372 |
|
|
If $H$ is not arranged in this way, it can be arranged in this way by elementary |
1373 |
|
|
row operations. |
1374 |
|
|
|
1375 |
|
|
We illustrate the application of the a parity generation matrix $H$ with the following |
1376 |
|
|
example. |
1377 |
|
|
|
1378 |
|
|
\begin{vworkexamplestatement} |
1379 |
|
|
\label{ex:cedc0:slco0:spcm0:01} |
1380 |
|
|
For a $(7,4)$ code where each message is a row vector |
1381 |
|
|
|
1382 |
|
|
\begin{equation} |
1383 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:01} |
1384 |
|
|
[ d_0 \; d_1 \; d_2 \; d_3 \; c_0 \; c_1 \; c_2 ] |
1385 |
|
|
\end{equation} |
1386 |
|
|
|
1387 |
|
|
\noindent{}and where the parity check matrix is |
1388 |
|
|
|
1389 |
|
|
\begin{equation} |
1390 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:02} |
1391 |
|
|
H = \left[\begin{array}{ccccccc} |
1392 |
|
|
1 & 1 & 0 & 1 & 1 & 0 & 0 \\ |
1393 |
|
|
1 & 0 & 1 & 1 & 0 & 1 & 0 \\ |
1394 |
|
|
0 & 1 & 1 & 1 & 0 & 0 & 1 |
1395 |
|
|
\end{array}\right], |
1396 |
|
|
\end{equation} |
1397 |
|
|
|
1398 |
|
|
\noindent{}find expressions for the check bits $c_0$, $c_1$, and $c_2$; and |
1399 |
|
|
enumerate the complete code. |
1400 |
|
|
\end{vworkexamplestatement} |
1401 |
|
|
\begin{vworkexampleparsection}{Solution} |
1402 |
|
|
Note that $H$ is already conditioned so that the rightmost $n-k$ columns |
1403 |
|
|
are the identity matrix. By the definition provided by |
1404 |
|
|
(\ref{eq:cedc0:slco0:spcm0:06}), |
1405 |
|
|
|
1406 |
|
|
\begin{equation} |
1407 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:02b} |
1408 |
|
|
H'_{(n-k \times k) = (3 \times 4)} = \left[\begin{array}{cccc} |
1409 |
|
|
1 & 1 & 0 & 1 \\ |
1410 |
|
|
1 & 0 & 1 & 1 \\ |
1411 |
|
|
0 & 1 & 1 & 1 |
1412 |
|
|
\end{array}\right] |
1413 |
|
|
\end{equation} |
1414 |
|
|
|
1415 |
|
|
\noindent{}and |
1416 |
|
|
|
1417 |
|
|
\begin{equation} |
1418 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:02c} |
1419 |
|
|
I_{(n-k \times n-k) = (3 \times 3)}= \left[\begin{array}{ccc} |
1420 |
|
|
1 & 0 & 0 \\ |
1421 |
|
|
0 & 1 & 0 \\ |
1422 |
|
|
0 & 0 & 1 |
1423 |
|
|
\end{array}\right]. |
1424 |
|
|
\end{equation} |
1425 |
|
|
|
1426 |
|
|
Applying (\ref{eq:cedc0:slco0:spcm0:01}) yields |
1427 |
|
|
|
1428 |
|
|
\begin{equation} |
1429 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:03} |
1430 |
|
|
\left[\begin{array}{ccccccc} |
1431 |
|
|
1 & 1 & 0 & 1 & 1 & 0 & 0 \\ |
1432 |
|
|
1 & 0 & 1 & 1 & 0 & 1 & 0 \\ |
1433 |
|
|
0 & 1 & 1 & 1 & 0 & 0 & 1 |
1434 |
|
|
\end{array}\right] |
1435 |
|
|
\left[\begin{array}{c}d_0\\d_1\\d_2\\d_3\\c_0\\c_1\\c_2\end{array}\right] = |
1436 |
|
|
\left[\begin{array}{c}0\\0\\0\\0\\0\\0\\0\end{array}\right] , |
1437 |
|
|
\end{equation} |
1438 |
|
|
|
1439 |
|
|
\noindent{}or equivalently the system of equations |
1440 |
|
|
|
1441 |
|
|
\begin{eqnarray} |
1442 |
|
|
\nonumber |
1443 |
|
|
d_0 \oplus d_1 \oplus d_3 \oplus c_0 & = & 0 \\ |
1444 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:05} |
1445 |
|
|
d_0 \oplus d_2 \oplus d_3 \oplus c_1 & = & 0 \\ |
1446 |
|
|
\nonumber |
1447 |
|
|
d_1 \oplus d_2 \oplus d_3 \oplus c_2 & = & 0 . |
1448 |
|
|
\end{eqnarray} |
1449 |
|
|
|
1450 |
|
|
\noindent{}The system of equations (\ref{eq:ex:cedc0:slco0:spcm0:01:05}) |
1451 |
|
|
can be solved for $c_0$, $c_1$, and $c_2$ by using |
1452 |
|
|
Property \ref{prop:cedc0:scon0:sxor0:01:04} |
1453 |
|
|
from Section \ref{cedc0:scon0:sxor0}, which allows $c_0$, $c_1$ and $c_2$ to |
1454 |
|
|
be moved to the other side of the equations in (\ref{eq:ex:cedc0:slco0:spcm0:01:05}), |
1455 |
|
|
yielding |
1456 |
|
|
|
1457 |
|
|
\begin{eqnarray} |
1458 |
|
|
\nonumber |
1459 |
|
|
c_0 & = & d_0 \oplus d_1 \oplus d_3 \\ |
1460 |
|
|
\label{eq:ex:cedc0:slco0:spcm0:01:08} |
1461 |
|
|
c_1 & = & d_0 \oplus d_2 \oplus d_3 \\ |
1462 |
|
|
\nonumber |
1463 |
|
|
c_2 & = & d_1 \oplus d_2 \oplus d_3 . |
1464 |
|
|
\end{eqnarray} |
1465 |
|
|
|
1466 |
|
|
The full code can be enumerated by listing all $2^k = 2^4 = 16$ combinations of |
1467 |
|
|
the data bits $d_0\ldots{}d_3$ and then applying (\ref{eq:ex:cedc0:slco0:spcm0:01:08}) |
1468 |
|
|
to obtain $c_0$, $c_1$, and $c_2$. Table \ref{tbl:ex:cedc0:slco0:spcm0:01:01} |
1469 |
|
|
supplies the full code obtained in this way. |
1470 |
|
|
|
1471 |
|
|
\begin{table} |
1472 |
|
|
\caption{Fully Enumerated (7,4) Code (Solution To Example \ref{ex:cedc0:slco0:spcm0:01})} |
1473 |
|
|
\label{tbl:ex:cedc0:slco0:spcm0:01:01} |
1474 |
|
|
\begin{center} |
1475 |
|
|
\begin{tabular}{|c|c|c|c|c|c|c|} |
1476 |
|
|
\hline |
1477 |
|
|
$d_0$ & $d_1$ & $d_2$ & $d_3$ & $c_0$ & $c_1$ & $c_2$ \\ |
1478 |
|
|
& & & & $=d_0 \oplus d_1 \oplus d_3$ & $=d_0 \oplus d_2 \oplus d_3$ & $=d_1 \oplus d_2 \oplus d_3$ \\ |
1479 |
|
|
\hline |
1480 |
|
|
\hline |
1481 |
|
|
0 & 0 & 0 & 0 & 0 & 0 & 0 \\ |
1482 |
|
|
\hline |
1483 |
|
|
0 & 0 & 0 & 1 & 1 & 1 & 0 \\ |
1484 |
|
|
\hline |
1485 |
|
|
0 & 0 & 1 & 0 & 0 & 1 & 1 \\ |
1486 |
|
|
\hline |
1487 |
|
|
0 & 0 & 1 & 1 & 1 & 0 & 1 \\ |
1488 |
|
|
\hline |
1489 |
|
|
0 & 1 & 0 & 0 & 1 & 0 & 1 \\ |
1490 |
|
|
\hline |
1491 |
|
|
0 & 1 & 0 & 1 & 0 & 1 & 1 \\ |
1492 |
|
|
\hline |
1493 |
|
|
0 & 1 & 1 & 0 & 1 & 1 & 0 \\ |
1494 |
|
|
\hline |
1495 |
|
|
0 & 1 & 1 & 1 & 0 & 0 & 0 \\ |
1496 |
|
|
\hline |
1497 |
|
|
1 & 0 & 0 & 0 & 1 & 1 & 1 \\ |
1498 |
|
|
\hline |
1499 |
|
|
1 & 0 & 0 & 1 & 0 & 0 & 1 \\ |
1500 |
|
|
\hline |
1501 |
|
|
1 & 0 & 1 & 0 & 1 & 0 & 0 \\ |
1502 |
|
|
\hline |
1503 |
|
|
1 & 0 & 1 & 1 & 0 & 1 & 0 \\ |
1504 |
|
|
\hline |
1505 |
|
|
1 & 1 & 0 & 0 & 0 & 1 & 0 \\ |
1506 |
|
|
\hline |
1507 |
|
|
1 & 1 & 0 & 1 & 1 & 0 & 0 \\ |
1508 |
|
|
\hline |
1509 |
|
|
1 & 1 & 1 & 0 & 0 & 0 & 1 \\ |
1510 |
|
|
\hline |
1511 |
|
|
1 & 1 & 1 & 1 & 1 & 1 & 1 \\ |
1512 |
|
|
\hline |
1513 |
|
|
\end{tabular} |
1514 |
|
|
\end{center} |
1515 |
|
|
\end{table} |
1516 |
|
|
\end{vworkexampleparsection} |
1517 |
|
|
\vworkexamplefooter{} |
1518 |
|
|
|
1519 |
|
|
In the first paragraph of this section, we made the claim that \emph{any} linear |
1520 |
|
|
code can be represented by a parity check matrix. We substantiate that |
1521 |
|
|
claim with the following lemma. |
1522 |
|
|
|
1523 |
|
|
\begin{vworklemmastatement} |
1524 |
|
|
\label{lem:cedc0:slco0:spcm0:01} |
1525 |
|
|
Every linear code can be represented by a parity check matrix, and every |
1526 |
|
|
parity check matrix defines a linear code. |
1527 |
|
|
\end{vworklemmastatement} |
1528 |
|
|
\begin{vworklemmaproof} |
1529 |
|
|
We first prove that a code $C$ specified by a parity check matrix $H$ |
1530 |
|
|
is a linear code. Note that $\mathbf{0} \in C$ (which is required for a linear code), |
1531 |
|
|
since $H \mathbf{0}^T = \mathbf{0}$. If $m_1 \in C$ and $m_2 \in C$, then |
1532 |
|
|
by definition $H m_1^T = H m_2^T = \mathbf{0}$. It can be shown by linearity |
1533 |
|
|
that $H (m_3^T = (m_1 + m_2)^T) = \mathbf{0}$, and thus $m_3 \in C$. |
1534 |
|
|
|
1535 |
|
|
We then prove the implication in the other direction; that any linear code must be |
1536 |
|
|
describable by a parity matrix $H$. Although this is true in the general |
1537 |
|
|
case, we prove it only for the case of the type of code involving |
1538 |
|
|
$n-k$ check bits appended to $k$ data bits, as described in |
1539 |
|
|
Section \ref{cedc0:scon0:sccb0} and Figure |
1540 |
|
|
\ref{fig:cedc0:scon0:sccb0:01}. This type of code contains a codeword |
1541 |
|
|
for all possible values of the data bits $d_0 \ldots d_{k-1}$. We |
1542 |
|
|
consider only those codewords which have a single data bit set. Figure |
1543 |
|
|
\ref{tbl:lem:cedc0:slco0:spcm0:01:01} enumerates such codewords extracted |
1544 |
|
|
from Example \ref{ex:cedc0:slco0:spcm0:01} and Figure |
1545 |
|
|
\ref{tbl:ex:cedc0:slco0:spcm0:01:01}. |
1546 |
|
|
|
1547 |
|
|
\begin{table} |
1548 |
|
|
\caption{Codewords From Example \ref{ex:cedc0:slco0:spcm0:01} With Only A Single Data Bit Set} |
1549 |
|
|
\label{tbl:lem:cedc0:slco0:spcm0:01:01} |
1550 |
|
|
\begin{center} |
1551 |
|
|
\begin{tabular}{|c|c|c|c|c|c|c|} |
1552 |
|
|
\hline |
1553 |
|
|
$d_0$ & $d_1$ & $d_2$ & $d_3$ & $c_0$ & $c_1$ & $c_2$ \\ |
1554 |
|
|
\hline |
1555 |
|
|
\hline |
1556 |
|
|
1 & 0 & 0 & 0 & 1 & 1 & 1 \\ |
1557 |
|
|
\hline |
1558 |
|
|
0 & 1 & 0 & 0 & 1 & 0 & 1 \\ |
1559 |
|
|
\hline |
1560 |
|
|
0 & 0 & 1 & 0 & 0 & 1 & 1 \\ |
1561 |
|
|
\hline |
1562 |
|
|
0 & 0 & 0 & 1 & 1 & 1 & 0 \\ |
1563 |
|
|
\hline |
1564 |
|
|
\end{tabular} |
1565 |
|
|
\end{center} |
1566 |
|
|
\end{table} |
1567 |
|
|
|
1568 |
|
|
Because of the linearity of the code, we are able to construct any |
1569 |
|
|
codeword of the code from a set of codewords such as are |
1570 |
|
|
shown in Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01}. Given |
1571 |
|
|
any four data bits $d_0 \ldots d_3$, we form the codeword |
1572 |
|
|
by adding together the rows corresponding to the 1's in the |
1573 |
|
|
data. For example, to form the codeword corresponding to |
1574 |
|
|
$[d_0 d_1 d_2 d_3]$ $=$ $[1010]$, we would simply XOR together |
1575 |
|
|
the the first and third rows from Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01}: |
1576 |
|
|
$[1000111] \oplus [0010011] = [1010100]$. |
1577 |
|
|
|
1578 |
|
|
However, the structure of Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01} |
1579 |
|
|
gives us somewhat more information about the structure of a parity |
1580 |
|
|
generation matrix $H$. In the first row, with only $d_0$ set to 1, |
1581 |
|
|
$c_0$, $c_1$, and $c_2$ are all 1: this indicates that $d_0$ must appear in the |
1582 |
|
|
parity equations for $c_0$, $c_1$, and $c_2$. Similarly, the second row indicates |
1583 |
|
|
that $d_1$ appears in the parity equations for $c_0$ and $c_2$ only. |
1584 |
|
|
One can thus derive (\ref{eq:ex:cedc0:slco0:spcm0:01:08}) directly |
1585 |
|
|
from examining the last three columns of Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01}. |
1586 |
|
|
Using the observations above, a parity check matrix which provides data consistent |
1587 |
|
|
with Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01} can be constructed. Since |
1588 |
|
|
the code being considered and the code formed by the parity check matrix |
1589 |
|
|
constructed as described above are both linear, it follows that the two codes |
1590 |
|
|
are identical. Thus, using the procedure described above, |
1591 |
|
|
a parity check matrix can be constructed for any linear code consisting of |
1592 |
|
|
$n-k$ check bits appended to $k$ data bits. |
1593 |
|
|
\end{vworklemmaproof} |
1594 |
|
|
\vworklemmafooter{} |
1595 |
|
|
|
1596 |
|
|
|
1597 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1598 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1599 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1600 |
|
|
\subsection{The Generator Matrix} |
1601 |
|
|
\label{cedc0:slco0:sgma0} |
1602 |
|
|
|
1603 |
|
|
A second characterization of a linear code is |
1604 |
|
|
by a \index{generator matrix}generator matrix. A generator matrix is |
1605 |
|
|
a set of codewords chosen to be a minimal basis set for the code so that |
1606 |
|
|
all other codewords can be calculated by linearly combining codewords |
1607 |
|
|
in the generator matrix. |
1608 |
|
|
|
1609 |
|
|
The generator matrix for the code from Example \ref{ex:cedc0:slco0:spcm0:01} is |
1610 |
|
|
|
1611 |
|
|
\begin{equation} |
1612 |
|
|
\label{eq:cedc0:slco0:sgma0:01} |
1613 |
|
|
G = \left[ |
1614 |
|
|
\begin{array}{ccccccc} |
1615 |
|
|
1 & 0 & 0 & 0 & 1 & 1 & 1 \\ |
1616 |
|
|
0 & 1 & 0 & 0 & 1 & 0 & 1 \\ |
1617 |
|
|
0 & 0 & 1 & 0 & 0 & 1 & 1 \\ |
1618 |
|
|
0 & 0 & 0 & 1 & 1 & 1 & 0 |
1619 |
|
|
\end{array} |
1620 |
|
|
\right] . |
1621 |
|
|
\end{equation} |
1622 |
|
|
|
1623 |
|
|
\noindent{}Note that this generator matrix also appears as Table |
1624 |
|
|
\ref{tbl:lem:cedc0:slco0:spcm0:01:01}. |
1625 |
|
|
|
1626 |
|
|
As with a parity check matrix $H$, we prefer a certain form for |
1627 |
|
|
a generator matrix $G$. This form is exemplified by |
1628 |
|
|
(\ref{eq:cedc0:slco0:sgma0:01}), where $G$ consists of |
1629 |
|
|
the identity matrix with a second matrix concatenated: |
1630 |
|
|
|
1631 |
|
|
\begin{equation} |
1632 |
|
|
\label{eq:cedc0:slco0:sgma0:01b} |
1633 |
|
|
G_{k \times n} = [ I_{k \times k} | G'_{k \times n-k}] . |
1634 |
|
|
\end{equation} |
1635 |
|
|
|
1636 |
|
|
For the same linear code, there is a simple relationship between the |
1637 |
|
|
parity check matrix $H$ and the generator matrix $G$, assuming that |
1638 |
|
|
$H$ and $G$ are in the forms suggested by equations |
1639 |
|
|
(\ref{eq:cedc0:slco0:spcm0:06}) and (\ref{eq:cedc0:slco0:sgma0:01b}), |
1640 |
|
|
respectively (the forms containing the identity matrix). This |
1641 |
|
|
simple relationship is |
1642 |
|
|
|
1643 |
|
|
\begin{equation} |
1644 |
|
|
\label{eq:cedc0:slco0:sgma0:02} |
1645 |
|
|
G' = (H')^T, |
1646 |
|
|
\end{equation} |
1647 |
|
|
|
1648 |
|
|
\noindent{}or equivalently |
1649 |
|
|
|
1650 |
|
|
\begin{equation} |
1651 |
|
|
\label{eq:cedc0:slco0:sgma0:03} |
1652 |
|
|
H' = (G')^T . |
1653 |
|
|
\end{equation} |
1654 |
|
|
|
1655 |
|
|
It is not difficult to intuitively understand |
1656 |
|
|
(\ref{eq:cedc0:slco0:sgma0:02}) and (\ref{eq:cedc0:slco0:sgma0:03}) |
1657 |
|
|
with the aid of Example \ref{ex:cedc0:slco0:spcm0:01} and the definition |
1658 |
|
|
of $H$ and $G$ in |
1659 |
|
|
(\ref{eq:ex:cedc0:slco0:spcm0:01:02}) and |
1660 |
|
|
(\ref{eq:cedc0:slco0:sgma0:01b}), respectively. To go from $H$ to $G$, |
1661 |
|
|
imagine applying the parity check relationship (Eq. \ref{eq:ex:cedc0:slco0:spcm0:01:03}, |
1662 |
|
|
for example) to the unit vector $[d_0 d_1 d_2 d_3] = [1 0 0 0]$. It is easy to see that |
1663 |
|
|
to satisfy the parity check relationship, $c_0$, $c_1$, and $c_2$ will need to be |
1664 |
|
|
set to the values of the first column in $H$, i.e. |
1665 |
|
|
$\left[\begin{array}{c}c_0\\c_1\\c_2\end{array}\right] = \left[\begin{array}{c}1\\1\\0\end{array}\right]$. |
1666 |
|
|
With $[d_0 d_1 d_2 d_3] = [0 1 0 0]$, $c_0$, $c_1$, and $c_2$ will need to be set |
1667 |
|
|
to the values of the second column in $H$, and so on. To go from $G$ to |
1668 |
|
|
$H$, the argument supplied in the proof of Lemma |
1669 |
|
|
\ref{lem:cedc0:slco0:spcm0:01} applies. |
1670 |
|
|
|
1671 |
|
|
Thus, as long as they are conditioned properly, the parity check matrix $H$ and the |
1672 |
|
|
generator matrix $G$ are equivalent, and one can translate between the two forms |
1673 |
|
|
by inspection. |
1674 |
|
|
|
1675 |
|
|
|
1676 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1677 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1678 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1679 |
|
|
\subsection{Properties Of Linear Codes} |
1680 |
|
|
\label{cedc0:slco0:splc0} |
1681 |
|
|
|
1682 |
|
|
In this section we present many important properties of linear codes. |
1683 |
|
|
Although most of these properties follow immediately from the observation |
1684 |
|
|
that a linear code is a subspace of $\mathbb{B}^n$ and could have been |
1685 |
|
|
presented in Section \ref{cedc0:slco0:sdef0}, the presentation of these properties |
1686 |
|
|
is best made in terms of the parity check matrix and the generator matrix, |
1687 |
|
|
and so the presentation of these properties was postponed until after the |
1688 |
|
|
parity check matrix and generator matrix were discussed. |
1689 |
|
|
|
1690 |
|
|
\begin{vworklemmastatement} |
1691 |
|
|
\label{lem:cedc0:slco0:splc0:01} |
1692 |
|
|
The sum of two or more codewords in a linear code is also a codeword. (This also includes |
1693 |
|
|
adding a codeword to itself.) |
1694 |
|
|
\end{vworklemmastatement} |
1695 |
|
|
\begin{vworklemmaproof} |
1696 |
|
|
This property follows immediately from the definition of a code as a subspace and |
1697 |
|
|
from Lemma \ref{lem:cedc0:sfft0:rmc0:01}. The generator matrix $G$ of a code |
1698 |
|
|
is a $k \times n$ matrix and will always have rank $k$. If we denote the rows of |
1699 |
|
|
the generator matrix as $r_0, r_1, \ldots, r_{k-1}$, then any codeword will be the |
1700 |
|
|
parameterized sum $\alpha_0 r_0 + \alpha_1 r_1 + \ldots + \alpha_{k-1} r_{k-1}$. |
1701 |
|
|
Any sum of codewords will be a sum of this form, and |
1702 |
|
|
superfluous repeated terms can be removed |
1703 |
|
|
(Property \ref{prop:enum:cedc0:sfft0:dff0:01:02}, p. \pageref{prop:enum:cedc0:sfft0:dff0:01:02}), |
1704 |
|
|
leaving only a simple parameterized sum of the form |
1705 |
|
|
$\alpha_0 r_0 + \alpha_1 r_1 + \ldots + \alpha_{k-1} r_{k-1}$, |
1706 |
|
|
with $\alpha_0, \ldots, \alpha_{k-1} \in \mathbb{B}$. |
1707 |
|
|
\end{vworklemmaproof} |
1708 |
|
|
|
1709 |
|
|
\begin{vworklemmastatement} |
1710 |
|
|
\label{lem:cedc0:slco0:splc0:02} |
1711 |
|
|
Any linear code includes $\mathbf{0_{1 \times n}}$ as a codeword. |
1712 |
|
|
\end{vworklemmastatement} |
1713 |
|
|
\begin{vworklemmaproof} |
1714 |
|
|
This property is inherent in the traditional linear algebra definition |
1715 |
|
|
of a subspace. As an alternative, we may simply add any codeword to itself |
1716 |
|
|
to obtain $\mathbf{0_{1 \times n}}$, which will then be a codeword |
1717 |
|
|
by Lemma \ref{lem:cedc0:slco0:splc0:01}. |
1718 |
|
|
\end{vworklemmaproof} |
1719 |
|
|
|
1720 |
|
|
\begin{vworklemmastatement} |
1721 |
|
|
\label{lem:cedc0:slco0:splc0:03} |
1722 |
|
|
In a linear code, the weight $w$ of a minimum weight codeword (excluding |
1723 |
|
|
$\mathbf{0_{1 \times n}}$) is the minimum Hamming distance |
1724 |
|
|
$\hat{d}$ of the code. |
1725 |
|
|
\end{vworklemmastatement} |
1726 |
|
|
\begin{vworklemmaproof} |
1727 |
|
|
Assume that there are two codewords $c_1, c_2$ such that |
1728 |
|
|
$d(c_1, c_2) < w$. The exclusive-OR of $c_1$ and $c_2$, |
1729 |
|
|
$c_1 \oplus c_2$, |
1730 |
|
|
must also be a codeword (by Lemma \ref{lem:cedc0:slco0:splc0:01}). |
1731 |
|
|
However, note also that $wt(c_1 \oplus c_2)$ is the number of bit |
1732 |
|
|
positions in which $c_1$ and $c_2$ differ, thus |
1733 |
|
|
$c_1 \oplus c_2$ is a codeword in the code with |
1734 |
|
|
$wt(c_1 \oplus c_2) < w$, which contradicts our initial assumption of |
1735 |
|
|
knowing a minimum-weight codeword in the code. |
1736 |
|
|
\end{vworklemmaproof} |
1737 |
|
|
|
1738 |
|
|
|
1739 |
|
|
|
1740 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1741 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1742 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1743 |
|
|
\subsection{Syndrome Decoding} |
1744 |
|
|
\label{cedc0:slco0:ssdc0} |
1745 |
|
|
|
1746 |
|
|
A defining equation for linear code membership is given by |
1747 |
|
|
(\ref{eq:cedc0:slco0:spcm0:01}), $H m^T = \mathbf{0}$. For codes harnessed |
1748 |
|
|
for error-detection only, this equation is adequate, as calculating |
1749 |
|
|
$H m^T$ and comparing against $\mathbf{0}$ (i.e. decoding) is an economical operation. |
1750 |
|
|
However, for codes harnessed for error-correction, we seek a way to ``round'' back to the |
1751 |
|
|
nearest codeword. |
1752 |
|
|
|
1753 |
|
|
|
1754 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1755 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1756 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1757 |
|
|
\subsection[Relationship Between The Parity Check Matrix And \protect\mbox{\protect$\hat{d}$}] |
1758 |
|
|
{Relationship Between The Parity Check Matrix And \protect\mbox{\protect\boldmath$\hat{d}$}} |
1759 |
|
|
\label{cedc0:slco0:spcd0} |
1760 |
|
|
|
1761 |
|
|
One of the most important properties of a code is its minimum Hamming distance |
1762 |
|
|
$\hat{d}$. Here we demonstrate the relationship between the parity check matrix |
1763 |
|
|
$H$, the generator matrix $G$, and the minimum Hamming distance $\hat{d}$ of a |
1764 |
|
|
linear code. |
1765 |
|
|
|
1766 |
|
|
Upon inspection of the mechanics of the membership condition for a linear |
1767 |
|
|
code, (\ref{eq:cedc0:slco0:spcm0:01}), it is apparent that |
1768 |
|
|
$Hm^T$ is the sum of all columns from $H$ corresponding to a `1' in |
1769 |
|
|
$m$. Thus code membership is tied to the ways in which columns of |
1770 |
|
|
$H$ can be added to give $\mathbf{0}$. |
1771 |
|
|
|
1772 |
|
|
The following lemma is immediately apparent. |
1773 |
|
|
|
1774 |
|
|
\begin{vworklemmastatement} |
1775 |
|
|
\label{lem:cedc0:slco0:spcd0:01} |
1776 |
|
|
If no fewer than $d$ columns of $H$ can be summed to give $\mathbf{0}$, |
1777 |
|
|
the code has a minimum Hamming distance of $\hat{d}=d$. |
1778 |
|
|
\end{vworklemmastatement} |
1779 |
|
|
\begin{vworklemmaproof} |
1780 |
|
|
Choose any codeword $m \in C$. By definition, |
1781 |
|
|
$Hm^T = \mathbf{0}$, as this is the membership |
1782 |
|
|
condition (\ref{eq:cedc0:slco0:spcm0:01}) for a linear code. We desire |
1783 |
|
|
to modify $m \in C$ by bit corruptions to form a second codeword $m' \in C$, |
1784 |
|
|
and again by definition |
1785 |
|
|
$H(m')^T = \mathbf{0}$. Each bit corruption of $m$ will either include (if a 0 is corrupted |
1786 |
|
|
to a 1) or exclude (if a 1 is corrupted to 0) a |
1787 |
|
|
column of $H$ from the sum which is the $n-k$ check bits. If $Hm^T = \mathbf{0}$, |
1788 |
|
|
then in order for $H(m')^T = \mathbf{0}$, the sum of the included or excluded columns |
1789 |
|
|
must be $\mathbf{0}$. If no fewer than $d$ columns of $H$ sum to $\mathbf{0}$, then |
1790 |
|
|
no fewer than $d$ bit corruptions can change any $m \in C$ to some $m' \in C$. |
1791 |
|
|
\end{vworklemmaproof} |
1792 |
|
|
\vworklemmafooter{} |
1793 |
|
|
|
1794 |
|
|
A second lemma is also obvious by examining the form of the |
1795 |
|
|
parity check matrix given in (\ref{eq:cedc0:slco0:spcm0:06}), although |
1796 |
|
|
the result can be proved without this specific form. |
1797 |
|
|
|
1798 |
|
|
\begin{vworklemmastatementpar}{Singleton Bound} |
1799 |
|
|
\label{lem:cedc0:slco0:spcd0:03} |
1800 |
|
|
\index{Singleton bound}No code can have a maximum Hamming distance $\hat{d}$ larger than |
1801 |
|
|
$n-k+1$. |
1802 |
|
|
\end{vworklemmastatementpar} |
1803 |
|
|
\begin{vworklemmaparsection}{Proof \#1 (For Linear Codes)} |
1804 |
|
|
Choose any codeword $m \in C$. By definition, |
1805 |
|
|
$Hm^T = \mathbf{0}$, as this is the membership |
1806 |
|
|
condition (\ref{eq:cedc0:slco0:spcm0:01}) for a linear code. We desire |
1807 |
|
|
to modify $m \in C$ by bit corruptions to form a second codeword $m' \in C$, |
1808 |
|
|
and again by definition |
1809 |
|
|
$H(m')^T = \mathbf{0}$. Each bit corruption of $m$ will either include (if a 0 is corrupted |
1810 |
|
|
to a 1) or exclude (if a 1 is corrupted to 0) a |
1811 |
|
|
column of $H$ from the sum which is the $n-k$ check bits. If $Hm^T = \mathbf{0}$, |
1812 |
|
|
then in order for $H(m')^T = \mathbf{0}$, the sum of the included or excluded columns |
1813 |
|
|
must be $\mathbf{0}$. If no fewer than $d$ columns of $H$ sum to $\mathbf{0}$, then |
1814 |
|
|
no fewer than $d$ bit corruptions can change any $m \in C$ to some $m' \in C$. |
1815 |
|
|
\end{vworklemmaparsection} |
1816 |
|
|
\begin{vworklemmaparsection}{Proof \#2 (For Any Code, Not Necessarily Linear)} |
1817 |
|
|
Choose any codeword $m \in C$. Choose any second codeword $m' \in C$, where |
1818 |
|
|
only one bit among the $k$ data bits is different between $m$ and $m'$. Note that we can |
1819 |
|
|
change $m$ into $m'$ through at most $n-k+1$ bit corruptions: one corruption among the $k$ |
1820 |
|
|
data bits and at most $n-k$ corruptions of all check bits. |
1821 |
|
|
\end{vworklemmaparsection} |
1822 |
|
|
\vworklemmafooter{} |
1823 |
|
|
|
1824 |
|
|
|
1825 |
|
|
|
1826 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1827 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1828 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1829 |
|
|
\subsection{Relationship Between The Parity Check Matrix And Burst Error Detection Capability} |
1830 |
|
|
\label{cedc0:slco0:spcb0} |
1831 |
|
|
|
1832 |
|
|
For any code, linear or non-linear, the Singleton bound |
1833 |
|
|
(Section \ref{cedc0:scob0:rbc0:saul0} and Lemma \ref{lem:cedc0:slco0:spcd0:03}) |
1834 |
|
|
assures us that $n-k$ check bits cannot always detect a burst error of |
1835 |
|
|
$n-k+1$ bits. This is an upper limit that cannot be violated. |
1836 |
|
|
|
1837 |
|
|
However, intuitively, it seems plausible that $n-k$ check bits could detect a |
1838 |
|
|
burst error of length $n-k$. Imagine that the burst error occurs within a span of |
1839 |
|
|
$n-k$ bits among the $k$ data bits. If each of the $2^{n-k}$ combinations of the |
1840 |
|
|
$n-k$ bits involved in the burst error maps to a different pattern among the $n-k$ |
1841 |
|
|
check bits, then every burst error of length $n-k$ among the data bits |
1842 |
|
|
would be detectable. Intuitively, a one-to-one mapping seems to be the criterion |
1843 |
|
|
for detection of a burst error of length $n-k$. |
1844 |
|
|
|
1845 |
|
|
For a linear code, the necessary condition for detection of a burst error |
1846 |
|
|
of length $n-k$ comes directly from Lemma |
1847 |
|
|
\ref{lem:cedc0:sfft0:rmc0:01}, and we present this necessary condition as the |
1848 |
|
|
following lemma. |
1849 |
|
|
|
1850 |
|
|
\begin{vworklemmastatement} |
1851 |
|
|
\label{lem:cedc0:slco0:spcb0:01} |
1852 |
|
|
A code can detect burst errors of length $b$ iff every $b$ contiguous |
1853 |
|
|
columns from the code's parity check matrix $H$ are linearly independent. |
1854 |
|
|
(For a code to detect burst errors of length $n-k$, any $n-k$ contiguous |
1855 |
|
|
columns from the code's parity check matrix must form a full-rank matrix.) |
1856 |
|
|
\end{vworklemmastatement} |
1857 |
|
|
\begin{vworklemmaproof} |
1858 |
|
|
Assume a codeword $c$ in the code $C$: then $Hc^T=\mathbf{0}$. |
1859 |
|
|
We desire to introduce a burst error of length $b$ into $c$, and we can |
1860 |
|
|
do this by summing an error vector $e$ with $c$, with the understanding that |
1861 |
|
|
$e$ may contain 1's only in the range of columns corresponding to the burst |
1862 |
|
|
error and 0's everywhere else. In order for the burst error to be undetected, we |
1863 |
|
|
require $H(c \oplus e)^T=\mathbf{0}$, or equivalently that |
1864 |
|
|
$He^T=\mathbf{0}$. In order for $He^T=\mathbf{0}$, either |
1865 |
|
|
$e = \mathbf{0}$ or else the columns of $H$ corresponding to the |
1866 |
|
|
1's in $e$ are linearly dependent and can sum to $\mathbf{0}$. |
1867 |
|
|
The case of $e=\mathbf{0}$ corresponds to no error, and the case |
1868 |
|
|
of $e \neq \mathbf{0}$ but $He^T=\mathbf{0}$ can happen only if |
1869 |
|
|
$b$ contiguous columns of $H$ corresponding to the location of the burst error |
1870 |
|
|
are not linearly independent. |
1871 |
|
|
\end{vworklemmaproof} |
1872 |
|
|
\vworklemmafooter{} |
1873 |
|
|
|
1874 |
|
|
|
1875 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1876 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1877 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1878 |
|
|
\subsection{Automatic Generation Of The Parity Check Matrix} |
1879 |
|
|
\label{cedc0:slco0:sagp0} |
1880 |
|
|
|
1881 |
|
|
|
1882 |
|
|
|
1883 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1884 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1885 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1886 |
|
|
\section{Hamming Codes} |
1887 |
|
|
%Section tag: hco0 |
1888 |
|
|
\label{cedc0:shco0} |
1889 |
|
|
|
1890 |
|
|
\index{Hamming code}\emph{Hamming codes} are a family of $\hat{d}=3$ (double |
1891 |
|
|
error detecting, single error correcting) codes which were discovered/developed |
1892 |
|
|
by Hamming. |
1893 |
|
|
|
1894 |
|
|
Consider the code represented by the parity check matrix |
1895 |
|
|
|
1896 |
|
|
\begin{equation} |
1897 |
|
|
\label{eq:cedc0:shco0:01} |
1898 |
|
|
H = \left[ |
1899 |
|
|
\begin{array}{ccccccc} |
1900 |
|
|
1 & 0 & 1 & 0 & 1 & 0 & 1 \\ |
1901 |
|
|
0 & 1 & 1 & 0 & 0 & 1 & 1 \\ |
1902 |
|
|
0 & 0 & 0 & 1 & 1 & 1 & 1 |
1903 |
|
|
\end{array} |
1904 |
|
|
\right] , |
1905 |
|
|
\end{equation} |
1906 |
|
|
|
1907 |
|
|
\noindent{}which is known as the Hamming $(7, 4)$ code. Notice that |
1908 |
|
|
the columns of $H$, if one considers the first row the least significant bit, are the |
1909 |
|
|
binary equivalents of the integers 1 through 7, arranged in order from left to right. Notice |
1910 |
|
|
also that $H$ is not in standard form |
1911 |
|
|
suggested by |
1912 |
|
|
(\ref{eq:cedc0:slco0:spcm0:06}), although the columns can be rearranged to |
1913 |
|
|
place it in standard form. |
1914 |
|
|
|
1915 |
|
|
One interesting feature of the code suggested by (\ref{eq:cedc0:shco0:01}) |
1916 |
|
|
is when one considers the syndrome of a received message $m$, $syn(m) = Hm^T$. |
1917 |
|
|
If the message is received correctly, $syn(m) = Hm^T = \mathbf{0}$. If the |
1918 |
|
|
message is received with one corrupted bit, the syndrome will give the ordinal |
1919 |
|
|
index of the corrupted bit: for example, a message with the third bit corrupted will |
1920 |
|
|
generate a syndrome of $\left[\begin{array}{c}1\\1\\0\end{array}\right]$, which is the |
1921 |
|
|
third column of $H$ and is the binary representation of 3 (and this leads to |
1922 |
|
|
convenient correction either in digital logic or in software). A message with two bits |
1923 |
|
|
corrupted will always represent a detectable corruption, but would be corrected |
1924 |
|
|
erroneously. A message with three or more corrupted bits may or may not be |
1925 |
|
|
detected and |
1926 |
|
|
can never be corrected. Specifically note that an error involving 3 or more bits |
1927 |
|
|
will not be detected if the sum of the columns of $H$ corresponding to the errors |
1928 |
|
|
is $\mathbf{0}$. |
1929 |
|
|
|
1930 |
|
|
However, by far the most interesting feature of the code suggested by |
1931 |
|
|
(\ref{eq:cedc0:shco0:01}) is that it provides a ``formula'' or ``pattern'' |
1932 |
|
|
approach for the construction of a code with $\hat{d}=3$. Note that |
1933 |
|
|
the code can be scaled up by choosing an $H$ with $i$ rows and populating |
1934 |
|
|
it with columns containing the binary representations of the integers |
1935 |
|
|
from 1 through $2^i - 1$, in order. The code suggested by (\ref{eq:cedc0:shco0:01}) |
1936 |
|
|
gives a pattern for the construction of a $(2^i - 1, 2^i - i - 1, 3)$ code |
1937 |
|
|
with as large a length as desired. |
1938 |
|
|
|
1939 |
|
|
The Hamming codes with $\hat{d}=3$ represent the codes with the largest $\hat{d}$ that |
1940 |
|
|
can be constructed without more sophisticated mathematical tools. We |
1941 |
|
|
develop these tools in Sections \ref{cedc0:sfft1} and |
1942 |
|
|
\ref{cedc0:scco0}. |
1943 |
|
|
|
1944 |
|
|
Hamming codes are perfect codes. If $i \in \vworkintsetpos$ is a parameter, |
1945 |
|
|
choose $n=2^i - 1$ and $k = 2^n - n - 1$ to form an |
1946 |
|
|
$(n,k,3) = (2^i - 1, 2^i - i - 1, 3)$ Hamming code. In order to give |
1947 |
|
|
a minimum Hamming distance $\hat{d}$ of 3, we require a packing radius $\rho$ of |
1948 |
|
|
1. The number of messages per packing sphere multiplied by the number of codewords gives the |
1949 |
|
|
total number of messages, i.e. |
1950 |
|
|
|
1951 |
|
|
\begin{equation} |
1952 |
|
|
\label{eq:cedc0:shco0:02} |
1953 |
|
|
\left[ \left(\begin{array}{c}2^i - 1\\0\end{array}\right) |
1954 |
|
|
+ \left(\begin{array}{c}2^i - 1\\1\end{array}\right) \right] |
1955 |
|
|
2^{2^i-i-1} = 2^{2^i-1}, |
1956 |
|
|
\end{equation} |
1957 |
|
|
|
1958 |
|
|
\noindent{}which the reader is encouraged to verify (Exercise \ref{exe:cedc0:sexe0:02}). |
1959 |
|
|
|
1960 |
|
|
The observation that Hamming codes exists for all values of the parameter |
1961 |
|
|
$i \in \vworkintsetpos$ and are perfect codes leads to a very easy-to-remember |
1962 |
|
|
rule of thumb which we present as a lemma. |
1963 |
|
|
|
1964 |
|
|
\begin{vworklemmastatement} |
1965 |
|
|
\label{lem:cedc0:shco0:01} |
1966 |
|
|
A block of $n=2^i$ requires $n-k=i+1$ check bits to protect at $\hat{d}=3$. |
1967 |
|
|
\end{vworklemmastatement} |
1968 |
|
|
\begin{vworklemmaproof} |
1969 |
|
|
A block of $n=2^i-1$ bits requires $n-k=i$ check bits to protect at $\hat{d}=3$, and |
1970 |
|
|
can be protected with a perfect Hamming code. At $n=2^i$ bits, $i$ check bits |
1971 |
|
|
are no longer adequate, because the code at $n=2^i-1$ is a perfect code and all |
1972 |
|
|
messages are consumed by the necessary packing space; thus at least $i+1$ check bits |
1973 |
|
|
are required. However, $i+1$ check bits will protect $n=2^{i+1}-1$ bits using a |
1974 |
|
|
perfect Hamming code, so $i+1$ bits are enough to protect $n=2^i$ bits. |
1975 |
|
|
\end{vworklemmaproof} |
1976 |
|
|
\vworklemmafooter{} |
1977 |
|
|
|
1978 |
|
|
We illustrate the application of Lemma \ref{lem:cedc0:shco0:01} with the following |
1979 |
|
|
example. |
1980 |
|
|
|
1981 |
|
|
\begin{vworkexamplestatement} |
1982 |
|
|
\label{ex:cedc0:shco0:01} |
1983 |
|
|
Estimate the number of check bits required |
1984 |
|
|
to protect a 128K ROM at $\hat{d}=3$. |
1985 |
|
|
\end{vworkexamplestatement} |
1986 |
|
|
\begin{vworkexampleparsection}{Solution} |
1987 |
|
|
128K $=2^{17}$ bytes $=2^{20}$ bits, thus $n=2^i=2^{20}$ in applying |
1988 |
|
|
Lemma \ref{lem:cedc0:shco0:01}. $i+1=21$ check bits are required to protect |
1989 |
|
|
the ROM at $\hat{d}=3$ (although there may be practical reasons for using more check bits). |
1990 |
|
|
\end{vworkexampleparsection} |
1991 |
|
|
\vworkexamplefooter{} |
1992 |
|
|
|
1993 |
|
|
|
1994 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1995 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1996 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1997 |
|
|
\section{Finite Field Theory Applied To Polynomials} |
1998 |
|
|
%Section tag: fft1 |
1999 |
|
|
\label{cedc0:sfft1} |
2000 |
|
|
|
2001 |
|
|
|
2002 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2003 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2004 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2005 |
|
|
\section{Cyclic Codes} |
2006 |
|
|
%Section tag: cco0 |
2007 |
|
|
\label{cedc0:scco0} |
2008 |
|
|
|
2009 |
|
|
Cyclic codes are the workhorses of linear codes, and are the codes used |
2010 |
|
|
most often in practice. Cyclic codes are attractive because: |
2011 |
|
|
|
2012 |
|
|
\begin{itemize} |
2013 |
|
|
\item Mathematically, they are best understood. |
2014 |
|
|
\item They have a convenient implementation in digital logic using shift |
2015 |
|
|
registers (which can be mimicked in software, but not especially |
2016 |
|
|
efficiently). |
2017 |
|
|
\end{itemize} |
2018 |
|
|
|
2019 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2020 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2021 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2022 |
|
|
\subsection{Definition And Properties Of Cyclic Codes} |
2023 |
|
|
%Subsection tag: dpo0 |
2024 |
|
|
\label{cedc0:scco0:sdpo0} |
2025 |
|
|
|
2026 |
|
|
The discussion of cyclic codes necessarily entails polynomial math, and |
2027 |
|
|
it is most convenient to think of the terms of a polynomial arranged with |
2028 |
|
|
the highest-order term first (and to think of the ``leftmost'' part of |
2029 |
|
|
a message as being transmitted first). For this reason, for the discussion of cyclic |
2030 |
|
|
codes, we prefer to think of a message as an ordered collection of bits |
2031 |
|
|
|
2032 |
|
|
\begin{equation} |
2033 |
|
|
\label{eq:cedc0:scco0:sdpo0:a01} |
2034 |
|
|
[m_{n-1}, m_{n-2}, \ldots{}, m_{0}] |
2035 |
|
|
\end{equation} |
2036 |
|
|
|
2037 |
|
|
\noindent{}rather than the ordered collection given in (\ref{eq:cedc0:scon0:sccb0:01}). |
2038 |
|
|
Similarly, we may also use the following notations for messages |
2039 |
|
|
|
2040 |
|
|
\begin{eqnarray} |
2041 |
|
|
\label{eq:cedc0:scco0:sdpo0:a02} |
2042 |
|
|
& [d_{k-1}, d_{k-2}, \ldots{}, d_{0}, c_{n-k-1}, c_{n-k-2}, \ldots{}, c_{0}] & \\ |
2043 |
|
|
\label{eq:cedc0:scco0:sdpo0:a02b} |
2044 |
|
|
& [d_{k-1}, d_{k-2}, \ldots{}, d_{0}] | [c_{n-k-1}, c_{n-k-2}, \ldots{}, c_{0}] & |
2045 |
|
|
\end{eqnarray} |
2046 |
|
|
|
2047 |
|
|
\noindent{}rather than the notations given in (\ref{eq:cedc0:scon0:sccb0:02}) |
2048 |
|
|
and (\ref{eq:cedc0:scon0:sccb0:02b}). Figure \ref{fig:cedc0:scon0:sccb0:01} |
2049 |
|
|
graphically illustrates this notation with bit nomenclature reversed. |
2050 |
|
|
|
2051 |
|
|
\begin{figure} |
2052 |
|
|
\centering |
2053 |
|
|
\includegraphics[width=4.6in]{c_edc0/cword02.eps} |
2054 |
|
|
\caption{Message Consisting Of The Concatenation Of $k$ Data Bits And $n-k$ |
2055 |
|
|
Check Bits, With Bit Notational Conventions For Cyclic Code Discusssion} |
2056 |
|
|
\label{fig:cedc0:scon0:sdpo0:01} |
2057 |
|
|
\end{figure} |
2058 |
|
|
|
2059 |
|
|
A \index{cyclic code}\emph{cyclic code} is a linear code such that whenever |
2060 |
|
|
the vector $[m_0 \; m_1 \; m_2 \; \ldots{} \; m_{n-1}]$ is in the code, |
2061 |
|
|
$[m_1 \; m_2 \; m_3 \; \ldots{} \; m_0]$ is also in the code. When |
2062 |
|
|
this definition is applied recursively, it means that for any codeword, all |
2063 |
|
|
cyclic shifts of the codeword are also in the code (that is, in fact, why |
2064 |
|
|
a \emph{cyclic} code is called a \emph{cyclic} code). For example, if |
2065 |
|
|
10001 is a codeword; then 00011, 00110, 01100, and 11000 must also be |
2066 |
|
|
codewords (notice that these last four codewords are left cyclic shifts of the |
2067 |
|
|
first codeword). Note that since the code is linear, all sums of codewords |
2068 |
|
|
must also be codewords. |
2069 |
|
|
|
2070 |
|
|
A cyclic code is characterized by a generator polynomial, which we call |
2071 |
|
|
$g(x)$, of the form |
2072 |
|
|
|
2073 |
|
|
\begin{equation} |
2074 |
|
|
\label{eq:cedc0:scco0:sdpo0:01} |
2075 |
|
|
g(x) = g_{n-k} x_{n-k} + g_{n-k-1} x_{n-k-1} + \; \ldots \; + g_1 x + g_0, |
2076 |
|
|
\end{equation} |
2077 |
|
|
|
2078 |
|
|
\noindent{}a polynomial of degree $n-k$, naturally containing up to $n-k+1$ terms. |
2079 |
|
|
Each coefficient $g_{n-k} \ldots g_{0}$ is chosen from $GF(2)$, so that |
2080 |
|
|
$g_{n-k} \ldots g_{0} \in \mathbb{B} = \{ 0 , 1 \}$. We assume that |
2081 |
|
|
$g_{n-k}$ and $g_{0}$ are both 1. We explain how the generator polynomial |
2082 |
|
|
specifies the code beginning in Section \ref{cedc0:scco0:ssut0}. |
2083 |
|
|
|
2084 |
|
|
Cyclic codes are harnessed in two distinct ways, which we will call |
2085 |
|
|
the \emph{strong} and \emph{weak} ways. |
2086 |
|
|
|
2087 |
|
|
In \emph{strong} utilization of cyclic codes |
2088 |
|
|
(Section \ref{cedc0:scco0:ssut0}), we must choose $g(x)$ in a very |
2089 |
|
|
special way with respect to $n$, and we cannot increase |
2090 |
|
|
$n$ arbitrarily (i.e. we are confined to messages of $n$ or |
2091 |
|
|
fewer bits). If we choose $g(x)$ in this way, we can |
2092 |
|
|
control the minimum Hamming distance $\hat{d}$ of the cyclic code we specify. |
2093 |
|
|
We call this utilization \emph{strong} because we are able to preserve a |
2094 |
|
|
strong property, the minimum Hamming distance $\hat{d}$ of the resulting code |
2095 |
|
|
(this is a very desirable feature, as it is in general not easy to construct a code |
2096 |
|
|
with a desirable large $\hat{d}$, and the theory of cyclic codes provides a way to do |
2097 |
|
|
this). |
2098 |
|
|
A typical ``strong'' utilization of a cyclic code may be in a communication peripheral |
2099 |
|
|
which can only accomodate a message of maximum length $\leq n$, and in this case |
2100 |
|
|
we can preserve strong properties of the cyclic code. |
2101 |
|
|
|
2102 |
|
|
In \emph{weak} utilization of cyclic codes |
2103 |
|
|
(Section \ref{cedc0:scco0:swut0}), $n$ is unconstrained, and the minimum Hamming |
2104 |
|
|
distance of the code may degrade as far as $\hat{d}=2$ as $n$ is |
2105 |
|
|
increased. We call such a utilization |
2106 |
|
|
\emph{weak} because only a \emph{weak} set of desirable properties can be preserved |
2107 |
|
|
in the resulting code. A typical example of a weak utilization would be the CRC-32 (a |
2108 |
|
|
32-bit checksum) used to signature large files. Such a utilization usually cannot |
2109 |
|
|
achieve even $\hat{d} = 3$, but can still preserve a low probability of undetected corruption |
2110 |
|
|
and protection against certain types of burst errors. |
2111 |
|
|
|
2112 |
|
|
Note that the choice of generator polynomial $g(x)$ |
2113 |
|
|
affects the properties of the code in both |
2114 |
|
|
the strong and weak utilizations, but in different ways. |
2115 |
|
|
|
2116 |
|
|
|
2117 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2118 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2119 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2120 |
|
|
\subsection{\emph{Strong} Utilization Of Cyclic Codes} |
2121 |
|
|
%Subsection tag: sut0 |
2122 |
|
|
\label{cedc0:scco0:ssut0} |
2123 |
|
|
|
2124 |
|
|
In the strong utilization of a cyclic code, |
2125 |
|
|
the vector corresponding to the generator polynomial $g(x)$, |
2126 |
|
|
$[0 \; \ldots \; 0 \; g_{n-k} \; g_{n-k-1} \; \ldots \; g_{0}]$ must |
2127 |
|
|
be in the code, as must all of its cyclic shifts and sums of its |
2128 |
|
|
cyclic shifts. A generator |
2129 |
|
|
matrix (not in standard form, and of course not the only generator |
2130 |
|
|
matrix) for a cyclic code is of the form |
2131 |
|
|
|
2132 |
|
|
\begin{equation} |
2133 |
|
|
\label{eq:cedc0:scco0:ssut0:02} |
2134 |
|
|
G = \left[ |
2135 |
|
|
\begin{array}{lllllllll} |
2136 |
|
|
g_{n-k} & g_{n-k-1} & g_{n-k-2} & \cdots & g_{0} & 0 & 0 & \cdots{} & 0 \\ |
2137 |
|
|
0 & g_{n-k} & g_{n-k-1} & \cdots & g_{1} & g_{0} & 0 & \cdots{} & 0 \\ |
2138 |
|
|
0 & 0 & g_{n-k} & \cdots & g_{2} & g_{1} & g_{0} & \cdots{} & 0 \\ |
2139 |
|
|
\vdots{} & & & & & & & & \\ |
2140 |
|
|
0 & 0 & 0 & \cdots & & & & \cdots{} & g_{0} |
2141 |
|
|
\end{array} |
2142 |
|
|
\right]_{k \times n} \!\!\!\!\!\!\!\!\!\!. |
2143 |
|
|
\end{equation} |
2144 |
|
|
|
2145 |
|
|
\noindent{}Note that the generator matrix in (\ref{eq:cedc0:scco0:ssut0:02}) |
2146 |
|
|
has rows which are cyclic shifts of the coefficients of $g(x)$ (and |
2147 |
|
|
for reasons discussed later, the other cyclic |
2148 |
|
|
shifts are also in the code). Note also that $G$ is a |
2149 |
|
|
$k \times n$ matrix, consistent with (\ref{eq:cedc0:slco0:sgma0:01b}). |
2150 |
|
|
|
2151 |
|
|
It is apparent from (\ref{eq:cedc0:scco0:ssut0:02}) that G can be |
2152 |
|
|
transformed into the form of (\ref{eq:cedc0:slco0:sgma0:01}) by |
2153 |
|
|
elementary row operations. Two arguments can be |
2154 |
|
|
made. First, by theorem, the determinant of an upper triangular matrix |
2155 |
|
|
(the first $k$ columns of $G$) is the product of the diagonal elements, |
2156 |
|
|
and since we've assumed $g_0 = g_{n-k} = 1$, this determinant is necessarily 1. |
2157 |
|
|
Since the first $k$ columns of $G$ have full rank, they can be transformed |
2158 |
|
|
into $I_{k \times k}$. Second, it is clear using elementary row operations how |
2159 |
|
|
to transform the first $k$ columns of $G$ into |
2160 |
|
|
$I_{k \times k}$ (Exercise \ref{exe:cedc0:sexe0:03}). |
2161 |
|
|
|
2162 |
|
|
\begin{vworkexamplestatement} |
2163 |
|
|
\label{ex:cedc0:scco0:ssut0:01} |
2164 |
|
|
For the $(7,4)$ code characterized by the generator polynomial |
2165 |
|
|
$g(x) = 1 + x + x^3$, form the generator matrix of the code |
2166 |
|
|
as in (\ref{eq:cedc0:scco0:ssut0:02}), reduce it by elementary |
2167 |
|
|
row operations to the form of (\ref{eq:cedc0:slco0:sgma0:01}), |
2168 |
|
|
and enumerate the $2^k = 16$ codewords. |
2169 |
|
|
\end{vworkexamplestatement} |
2170 |
|
|
\begin{vworkexampleparsection}{Solution} |
2171 |
|
|
With generator polynomial $g(x) = 1 + x + x^3$, $g_0 = 0$, $g_1 = 1$, |
2172 |
|
|
$g_2 = 0$, and $g_3 = 1$. By (\ref{eq:cedc0:scco0:ssut0:02}), |
2173 |
|
|
|
2174 |
|
|
\begin{equation} |
2175 |
|
|
\label{eq:ex:cedc0:scco0:ssut0:01:01} |
2176 |
|
|
G = \left[ |
2177 |
|
|
\begin{array}{ccccccc} |
2178 |
|
|
g_0 & g_1 & g_2 & g_3 & 0 & 0 & 0 \\ |
2179 |
|
|
0 & g_0 & g_1 & g_2 & g_3 & 0 & 0 \\ |
2180 |
|
|
0 & 0 & g_0 & g_1 & g_2 & g_3 & 0 \\ |
2181 |
|
|
0 & 0 & 0 & g_0 & g_1 & g_2 & g_3 |
2182 |
|
|
\end{array} |
2183 |
|
|
\right] |
2184 |
|
|
= |
2185 |
|
|
\left[ |
2186 |
|
|
\begin{array}{ccccccc} |
2187 |
|
|
1 & 1 & 0 & 1 & 0 & 0 & 0 \\ |
2188 |
|
|
0 & 1 & 1 & 0 & 1 & 0 & 0 \\ |
2189 |
|
|
0 & 0 & 1 & 1 & 0 & 1 & 0 \\ |
2190 |
|
|
0 & 0 & 0 & 1 & 1 & 0 & 1 |
2191 |
|
|
\end{array} |
2192 |
|
|
\right] . |
2193 |
|
|
\end{equation} |
2194 |
|
|
|
2195 |
|
|
Adding (in the sense of $GF(2)$, see Section \ref{cedc0:sfft0:dff0}) |
2196 |
|
|
the second row to the first yields |
2197 |
|
|
|
2198 |
|
|
\begin{equation} |
2199 |
|
|
\label{eq:ex:cedc0:scco0:ssut0:01:02} |
2200 |
|
|
G = \left[ |
2201 |
|
|
\begin{array}{ccccccc} |
2202 |
|
|
1 & 0 & 1 & 1 & 1 & 0 & 0 \\ |
2203 |
|
|
0 & 1 & 1 & 0 & 1 & 0 & 0 \\ |
2204 |
|
|
0 & 0 & 1 & 1 & 0 & 1 & 0 \\ |
2205 |
|
|
0 & 0 & 0 & 1 & 1 & 0 & 1 |
2206 |
|
|
\end{array} |
2207 |
|
|
\right] . |
2208 |
|
|
\end{equation} |
2209 |
|
|
|
2210 |
|
|
Adding the third row to the first row and to the second row (two |
2211 |
|
|
row operations) yields |
2212 |
|
|
|
2213 |
|
|
\begin{equation} |
2214 |
|
|
\label{eq:ex:cedc0:scco0:ssut0:01:03} |
2215 |
|
|
G = \left[ |
2216 |
|
|
\begin{array}{ccccccc} |
2217 |
|
|
1 & 0 & 0 & 0 & 1 & 1 & 0 \\ |
2218 |
|
|
0 & 1 & 0 & 1 & 1 & 1 & 0 \\ |
2219 |
|
|
0 & 0 & 1 & 1 & 0 & 1 & 0 \\ |
2220 |
|
|
0 & 0 & 0 & 1 & 1 & 0 & 1 |
2221 |
|
|
\end{array} |
2222 |
|
|
\right] . |
2223 |
|
|
\end{equation} |
2224 |
|
|
|
2225 |
|
|
Finally, adding the fourth row to the second row and to the third row (two |
2226 |
|
|
row operations) yields |
2227 |
|
|
|
2228 |
|
|
\begin{equation} |
2229 |
|
|
\label{eq:ex:cedc0:scco0:ssut0:01:04} |
2230 |
|
|
G = \left[ |
2231 |
|
|
\begin{array}{ccccccc} |
2232 |
|
|
1 & 0 & 0 & 0 & 1 & 1 & 0 \\ |
2233 |
|
|
0 & 1 & 0 & 0 & 0 & 1 & 1 \\ |
2234 |
|
|
0 & 0 & 1 & 0 & 1 & 1 & 1 \\ |
2235 |
|
|
0 & 0 & 0 & 1 & 1 & 0 & 1 |
2236 |
|
|
\end{array} |
2237 |
|
|
\right] . |
2238 |
|
|
\end{equation} |
2239 |
|
|
|
2240 |
|
|
The $2^4 = 16$ codewords can be enumerated by forming all linear combinations |
2241 |
|
|
of the rows of any of the matrices |
2242 |
|
|
(\ref{eq:ex:cedc0:scco0:ssut0:01:01}) |
2243 |
|
|
through (\ref{eq:ex:cedc0:scco0:ssut0:01:04}). These 16 codewords are |
2244 |
|
|
enumerated in Table \ref{tbl:ex:cedc0:scco0:ssut0:01:01}. |
2245 |
|
|
|
2246 |
|
|
\begin{table} |
2247 |
|
|
\caption{$2^4 = 16$ Codewords For Code Of Example \ref{ex:cedc0:scco0:ssut0:01}} |
2248 |
|
|
\label{tbl:ex:cedc0:scco0:ssut0:01:01} |
2249 |
|
|
\begin{center} |
2250 |
|
|
\begin{tabular}{|c|c|} |
2251 |
|
|
\hline |
2252 |
|
|
Data & Codeword \\ |
2253 |
|
|
(Value Of $k$ Data Bits) & \\ |
2254 |
|
|
\hline |
2255 |
|
|
\hline |
2256 |
|
|
0 & 0000 000 \\ |
2257 |
|
|
\hline |
2258 |
|
|
1 & 0001 101 \\ |
2259 |
|
|
\hline |
2260 |
|
|
2 & 0010 111 \\ |
2261 |
|
|
\hline |
2262 |
|
|
3 & 0011 010 \\ |
2263 |
|
|
\hline |
2264 |
|
|
4 & 0100 011 \\ |
2265 |
|
|
\hline |
2266 |
|
|
5 & 0101 110 \\ |
2267 |
|
|
\hline |
2268 |
|
|
6 & 0110 100 \\ |
2269 |
|
|
\hline |
2270 |
|
|
7 & 0111 001 \\ |
2271 |
|
|
\hline |
2272 |
|
|
8 & 1000 110 \\ |
2273 |
|
|
\hline |
2274 |
|
|
9 & 1001 011 \\ |
2275 |
|
|
\hline |
2276 |
|
|
10 & 1010 001 \\ |
2277 |
|
|
\hline |
2278 |
|
|
11 & 1011 100 \\ |
2279 |
|
|
\hline |
2280 |
|
|
12 & 1100 101 \\ |
2281 |
|
|
\hline |
2282 |
|
|
13 & 1101 000 \\ |
2283 |
|
|
\hline |
2284 |
|
|
14 & 1110 010 \\ |
2285 |
|
|
\hline |
2286 |
|
|
15 & 1111 111 \\ |
2287 |
|
|
\hline |
2288 |
|
|
\end{tabular} |
2289 |
|
|
\end{center} |
2290 |
|
|
\end{table} |
2291 |
|
|
\end{vworkexampleparsection} |
2292 |
|
|
\vworkexamplefooter{} |
2293 |
|
|
|
2294 |
|
|
|
2295 |
|
|
|
2296 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2297 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2298 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2299 |
|
|
\subsection{\emph{Weak} Utilization Of Cyclic Codes} |
2300 |
|
|
%Subsection tag: wut0 |
2301 |
|
|
\label{cedc0:scco0:swut0} |
2302 |
|
|
|
2303 |
|
|
|
2304 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2305 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2306 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2307 |
|
|
\subsection{Perfect Codes} |
2308 |
|
|
%Subsection tag: pfc0 |
2309 |
|
|
\label{cedc0:scob0:spfc0} |
2310 |
|
|
|
2311 |
|
|
We define a \index{perfect code}\emph{perfect code} as a code |
2312 |
|
|
where (\ref{eq:cedc0:scob0:rbc0:shsp0:01}) |
2313 |
|
|
is an equality---that is, where the volume of the $2^k$ packing spheres precisely |
2314 |
|
|
consumes the $2^n$ messages available. A perfect code has no ``waste'': that is, |
2315 |
|
|
there are no messages which do not participate in maintaining the required separation |
2316 |
|
|
between codewords. |
2317 |
|
|
|
2318 |
|
|
In this section, we address two issues: |
2319 |
|
|
|
2320 |
|
|
\begin{itemize} |
2321 |
|
|
\item The existence of integer solutions to |
2322 |
|
|
|
2323 |
|
|
\begin{equation} |
2324 |
|
|
\label{eq:cedc0:scob0:spfc0:01} |
2325 |
|
|
2^k V(n, \rho) = 2^n , |
2326 |
|
|
\end{equation} |
2327 |
|
|
|
2328 |
|
|
which is a question from number theory. |
2329 |
|
|
|
2330 |
|
|
\item Given $n$,$k$ which satisfy (\ref{eq:cedc0:scob0:spfc0:01}), the existence |
2331 |
|
|
of the codes whose possible existence is predicted. It should be remembered |
2332 |
|
|
that (\ref{eq:cedc0:scob0:spfc0:01}) is a necessary but not sufficient |
2333 |
|
|
condition. |
2334 |
|
|
\end{itemize} |
2335 |
|
|
|
2336 |
|
|
|
2337 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2338 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2339 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2340 |
|
|
\subsubsection[Existence Of Integer Solutions To |
2341 |
|
|
\protect\mbox{\protect$2^k V(n, \rho) = 2^n$}] |
2342 |
|
|
{Existence Of Integer Solutions To |
2343 |
|
|
\protect\mbox{\protect\boldmath$2^k V(n, \rho) = 2^n$}} |
2344 |
|
|
%Subsubsection tag: pfc0 |
2345 |
|
|
\label{cedc0:scob0:spfc0:seis0} |
2346 |
|
|
|
2347 |
|
|
|
2348 |
|
|
|
2349 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2350 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2351 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2352 |
|
|
\subsubsection{Existence Of Predicted Perfect Codes} |
2353 |
|
|
%Subsubsection tag: epc0 |
2354 |
|
|
\label{cedc0:scob0:spfc0:sepc0} |
2355 |
|
|
|
2356 |
|
|
|
2357 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2358 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2359 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2360 |
|
|
\section{Economical Implementation Of Linear Codes In Software} |
2361 |
|
|
%Section tag: eim0 |
2362 |
|
|
\label{cedc0:seim0} |
2363 |
|
|
|
2364 |
|
|
|
2365 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2366 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2367 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2368 |
|
|
\section[\protect\mbox{\protect$\hat{d}=2$} Codes Useful In Microcontroller Work] |
2369 |
|
|
{\protect\mbox{\protect\boldmath$\hat{d}=2$} Codes Useful In Microcontroller Work} |
2370 |
|
|
%Section tag: dtc0 |
2371 |
|
|
\label{cedc0:sdtc0} |
2372 |
|
|
|
2373 |
|
|
|
2374 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2375 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2376 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2377 |
|
|
\section[\protect\mbox{\protect$\hat{d}=3$} Codes Useful In Microcontroller Work] |
2378 |
|
|
{\protect\mbox{\protect\boldmath$\hat{d}=3$} Codes Useful In Microcontroller Work} |
2379 |
|
|
%Section tag: dhc0 |
2380 |
|
|
\label{cedc0:sdhc0} |
2381 |
|
|
|
2382 |
|
|
|
2383 |
|
|
|
2384 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2385 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2386 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2387 |
|
|
\section{Acknowledgements} |
2388 |
|
|
\label{cedc0:sack0} |
2389 |
|
|
|
2390 |
|
|
I'm very grateful to the following individuals who contributed insight |
2391 |
|
|
about error-detecting and error-correcting |
2392 |
|
|
codes on \index{comp.arch.embedded@\texttt{comp.arch.embedded}}\texttt{comp.arch.embedded} |
2393 |
|
|
and other |
2394 |
|
|
newsgroups: |
2395 |
|
|
Alan Coppola, |
2396 |
|
|
Eric Doenges, |
2397 |
|
|
Glen Herrmannsfeldt, |
2398 |
|
|
Dan Kotlow, |
2399 |
|
|
John Larkin, |
2400 |
|
|
Steven Murray, |
2401 |
|
|
Sphero Pefhany, |
2402 |
|
|
Jan-Hinnerk Reichert, |
2403 |
|
|
Thad Smith, |
2404 |
|
|
and |
2405 |
|
|
Jim Stewart. |
2406 |
|
|
|
2407 |
|
|
I'm grateful to |
2408 |
|
|
\index{Sperber, Ron} Ron Sperber \cite{bibref:i:ronsperber} and |
2409 |
|
|
\index{Chapman, Robin} Robin Chapman \cite{bibref:i:robinchapman} |
2410 |
|
|
for assistance with field theory offered on the |
2411 |
|
|
\texttt{sci.math} newsgroup \cite{bibref:n:scimathnewsgroup}. |
2412 |
|
|
|
2413 |
|
|
I'm also grateful to Mr. Michael J. Downes of the |
2414 |
|
|
\index{comp.text.tex@\texttt{comp.text.tex}}\texttt{comp.text.tex} |
2415 |
|
|
newsgroup, who assisted me with a technical difficulty involving |
2416 |
|
|
the \LaTeX ``$\backslash$\texttt{protect}'' command. |
2417 |
|
|
|
2418 |
|
|
|
2419 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2420 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2421 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2422 |
|
|
\section{Exercises} |
2423 |
|
|
\label{cedc0:sexe0} |
2424 |
|
|
|
2425 |
|
|
\begin{vworkexercisestatement} |
2426 |
|
|
\label{exe:cedc0:sexe0:01} |
2427 |
|
|
Show that the minimum Hamming distance of the code $\{0001, 0110, 1010, 1101\}$ |
2428 |
|
|
is 2. |
2429 |
|
|
\end{vworkexercisestatement} |
2430 |
|
|
|
2431 |
|
|
\begin{vworkexercisestatement} |
2432 |
|
|
\label{exe:cedc0:sexe0:02} |
2433 |
|
|
Verify Equation \ref{eq:cedc0:shco0:02}. |
2434 |
|
|
\end{vworkexercisestatement} |
2435 |
|
|
|
2436 |
|
|
\begin{vworkexercisestatement} |
2437 |
|
|
\label{exe:cedc0:sexe0:03} |
2438 |
|
|
Outline a procedure for transforming the $G$ of |
2439 |
|
|
(\ref{eq:cedc0:scco0:sdpo0:02}) into |
2440 |
|
|
the form of (\ref{eq:cedc0:slco0:sgma0:01}). |
2441 |
|
|
\end{vworkexercisestatement} |
2442 |
|
|
\vworkexercisefooter{} |
2443 |
|
|
|
2444 |
|
|
\vworkexercisefooter{} |
2445 |
|
|
|
2446 |
|
|
|
2447 |
|
|
|
2448 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2449 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2450 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2451 |
|
|
|
2452 |
|
|
\noindent\begin{figure}[!b] |
2453 |
|
|
\noindent\rule[-0.25in]{\textwidth}{1pt} |
2454 |
|
|
\begin{tiny} |
2455 |
|
|
\begin{verbatim} |
2456 |
|
|
$RCSfile: c_edc0.tex,v $ |
2457 |
|
|
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_edc0/c_edc0.tex,v $ |
2458 |
|
|
$Revision: 1.22 $ |
2459 |
|
|
$Author: dtashley $ |
2460 |
|
|
$Date: 2003/11/03 02:14:24 $ |
2461 |
|
|
\end{verbatim} |
2462 |
|
|
\end{tiny} |
2463 |
|
|
\noindent\rule[0.25in]{\textwidth}{1pt} |
2464 |
|
|
\end{figure} |
2465 |
|
|
|
2466 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2467 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2468 |
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
2469 |
|
|
% $Log: c_edc0.tex,v $ |
2470 |
|
|
% Revision 1.22 2003/11/03 02:14:24 dtashley |
2471 |
|
|
% All duplicate labels as flagged by LaTeX removed. Additional files added |
2472 |
|
|
% to Microsoft Visual Studio edit context. |
2473 |
|
|
% |
2474 |
|
|
% Revision 1.21 2002/12/14 07:28:46 dtashley |
2475 |
|
|
% Safety checkin. |
2476 |
|
|
% |
2477 |
|
|
% Revision 1.20 2002/12/10 08:00:44 dtashley |
2478 |
|
|
% Safety checkin. |
2479 |
|
|
% |
2480 |
|
|
% Revision 1.19 2002/12/02 06:29:47 dtashley |
2481 |
|
|
% Checking before resuming work at home. |
2482 |
|
|
% |
2483 |
|
|
% Revision 1.18 2002/12/01 21:29:08 dtashley |
2484 |
|
|
% Safety checkin. |
2485 |
|
|
% |
2486 |
|
|
% Revision 1.17 2002/12/01 02:55:02 dtashley |
2487 |
|
|
% Safety checkin. |
2488 |
|
|
% |
2489 |
|
|
% Revision 1.16 2002/11/29 04:01:38 dtashley |
2490 |
|
|
% Safety checkin, before engineering building power outage. |
2491 |
|
|
% |
2492 |
|
|
% Revision 1.15 2002/11/27 02:34:10 dtashley |
2493 |
|
|
% Safety checkin after substantial edits. |
2494 |
|
|
% |
2495 |
|
|
% Revision 1.14 2002/11/25 04:32:25 dtashley |
2496 |
|
|
% Substantial edits. |
2497 |
|
|
% |
2498 |
|
|
% Revision 1.13 2002/11/24 18:44:21 dtashley |
2499 |
|
|
% Substantial edits. Preparing for major reorganization of sections, and |
2500 |
|
|
% am checking this in to prevent accidental loss of information. |
2501 |
|
|
% |
2502 |
|
|
% Revision 1.12 2002/11/22 02:21:30 dtashley |
2503 |
|
|
% Substantial edits. |
2504 |
|
|
% |
2505 |
|
|
% Revision 1.11 2002/11/21 18:02:49 dtashley |
2506 |
|
|
% Safety checkin. Substantial edits. |
2507 |
|
|
% |
2508 |
|
|
% Revision 1.10 2002/11/19 22:08:42 dtashley |
2509 |
|
|
% Safety checkin before resuming work. |
2510 |
|
|
% |
2511 |
|
|
% Revision 1.9 2002/11/03 02:37:07 dtashley |
2512 |
|
|
% Substantial edits. Preparing to derive and incorporate material about |
2513 |
|
|
% upper limit on Hamming distance that can be achieved with a given number |
2514 |
|
|
% of check bits. |
2515 |
|
|
% |
2516 |
|
|
% Revision 1.8 2002/11/02 02:27:03 dtashley |
2517 |
|
|
% Weekly safety checkin. |
2518 |
|
|
% |
2519 |
|
|
% Revision 1.7 2002/10/31 04:02:23 dtashley |
2520 |
|
|
% Evening safety checkin. |
2521 |
|
|
% |
2522 |
|
|
% Revision 1.6 2002/10/30 02:06:12 dtashley |
2523 |
|
|
% Substantial edits of error-detecting and error-correcting codes chapter. |
2524 |
|
|
% |
2525 |
|
|
% Revision 1.5 2002/10/18 05:50:48 dtashley |
2526 |
|
|
% Substantial edits and progress. |
2527 |
|
|
% |
2528 |
|
|
% Revision 1.4 2002/10/16 01:28:24 dtashley |
2529 |
|
|
% Evening safety checkin. |
2530 |
|
|
% |
2531 |
|
|
% Revision 1.3 2002/10/14 23:32:48 dtashley |
2532 |
|
|
% Substantial edits. Resuming work on coding theory chapter. |
2533 |
|
|
% |
2534 |
|
|
% Revision 1.2 2002/09/25 08:01:09 dtashley |
2535 |
|
|
% Evening safety checkin after substantial work on coding chapter. |
2536 |
|
|
% |
2537 |
|
|
% Revision 1.1 2002/09/25 05:23:29 dtashley |
2538 |
|
|
% Initial checkin. |
2539 |
|
|
% |
2540 |
|
|
%End of file C_EDC0.TEX |