/[dtapublic]/pubs/books/ucbka/trunk/c_edc0/c_edc0.tex
ViewVC logotype

Annotation of /pubs/books/ucbka/trunk/c_edc0/c_edc0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4 - (hide annotations) (download) (as text)
Thu Oct 6 03:15:02 2016 UTC (7 years, 9 months ago) by dashley
File MIME type: application/x-tex
File size: 112787 byte(s)
Initial commit after migrating from CVS.
1 dashley 4 %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_edc0/c_edc0.tex,v 1.22 2003/11/03 02:14:24 dtashley Exp $
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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25