# Contents of /pubs/books/ucbka/trunk/c_edc0/c_edc0.tex

Tue Aug 13 02:35:39 2019 UTC (2 years, 10 months ago) by dashley
File MIME type: application/x-tex
File size: 107798 byte(s)
Change keyword substitution (migration from cvs to svn).

 1 %$Header$ 2 3 \chapter[\cedczeroshorttitle{}]{\cedczerolongtitle{}} 4 5 \label{cedc0} 6 7 \beginchapterquote{True genius resides in the capacity for evaluation of uncertain, 8 hazardous, and conflicting information.''} 9 {Winston Churchill} 10 \index{Churchill, Winston} 11 12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 13 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 14 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 15 \section{Introduction} 16 %Section tag: INT0 17 \label{cedc0:sint0} 18 19 In microcontroller work, it is frequently necessary to consider how 20 best to add redundancy to data. The following design scenarios are 21 common. 22 23 \begin{enumerate} 24 \item Immediately on powerup, a microcontroller product calculates 25 the checksum of its program memory (usually ROM or FLASH) and compares this 26 checksum to a stored value in order to detect possible corruption of program 27 memory. What is the best way to calculate a checksum for this 28 purpose? 29 \item A storage medium that will tolerate a limited number of write cycles 30 (such as EEPROM), will used to used to store data which will change 31 and need to rewritten more times than the life of the medium will 32 accomodate. As a result, a strategy which wears out a portion of the medium 33 and then uses another portion is employed. When a portion of the medium 34 wears out (as evidenced by corruption of bits), how can the data be 35 reliably recovered before 36 being transferred to the next portion? 37 \item A microcontroller product stores data in battery-backed RAM while powered 38 down. What type of checksum should be added to this data to provide the maximum 39 protection against data corruption? 40 \item Microcontrollers on the same circuit board communicate with each other 41 using UARTs. What form of checksum should be used to add protection 42 against electrical noise? 43 \end{enumerate} 44 45 46 This chapter deals with the mathematical basis for four 47 questions. 48 49 \begin{enumerate} 50 \item What is the mathematical basis for redundancy to allow error 51 detection and error correction? 52 \item How can redundancy be added to data to enable detection of errors? 53 \item How can redundancy be added to data to enable correction of 54 errors? 55 \item How can adding redundancy (encoding) and detecting and correcting 56 errors (decoding) be performed efficiently in 57 microcontroller software? 58 \end{enumerate} 59 60 Note that although the results presented in this chapter for the most part 61 have their origins in the study of communication channels, the problem of 62 protecting computer storage that may degrade (disc, tape, battery-backed RAM, 63 EEPROM, etc.) is mathematically the same problem as protecting data transmitted 64 through a communication channel. In either case $k$ data bits are protected 65 by $n-k$ check bits (see Figure \ref{fig:cedc0:scon0:sccb0:01}), 66 and the essence of the mathematical problem is how best to 67 select the check bits. 68 69 70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 71 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 72 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 73 \section{Coding Concepts} 74 %Section tag: con0 75 \label{cedc0:scon0} 76 77 \index{coding theory}\emph{Coding theory} is the branch of mathematics 78 concerned with transmitting data across noisy channels and recovering 79 the data \cite{bibref:w:ctfirst50}. In this section we introduce the 80 basic concepts and terminology which apply to microcontroller work. 81 82 83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 84 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 86 \subsection{Bits, Communication Channels, Messages, And Check Bits} 87 %Subection tag: ccb0 88 \label{cedc0:scon0:sccb0} 89 90 We assume that the data we wish to transmit is an ordered sequence of \index{bit}bits. 91 Each bit is a symbol of the \index{binary alphabet}binary alphabet, 92 $\mathbb{B} = \{0,1\}$. Many results in coding theory have been generalized to 93 alphabets with more than two symbols, but for microcontroller work it is adequate 94 to consider only $\mathbb{B}$, and in this chapter only 95 $\mathbb{B}$ is considered. 96 97 Bits are transmitted through a \index{communication channel}\index{channel}% 98 \emph{communication channel} (or simply \emph{channel}), which may with probability $p$ 99 corrupt a transmitted bit from 0 to 1 or vice-versa; or with 100 probability $q=1-p$ fail to corrupt a bit. For analysis, 101 we make the simplest mathematical assumptions and assume that 102 the probability of corruption from 0 to 1 is the same as the probability 103 of corruption from 1 to 0 (i.e. $p_{0\rightarrow{}1} = p_{1\rightarrow{}0} = p$), 104 and that corruption of each bit is independent. Alternately, we may imagine that rather 105 than being potentially corrupted during transmission, each bit is potentially 106 corrupted by the degradation of computer storage. 107 108 We assume that data is transmitted in blocks of 109 $n$ bits, consisting of $k$ data bits with $n-k$ check bits 110 (redundancy bits) appended (Figure \ref{fig:cedc0:scon0:sccb0:01}). This concatenation of 111 $k$ data bits and $n-k$ check bits is called a \index{message}\emph{message}. 112 Most commonly 113 in practice, $8 \vworkdivides n,k$ (and consequently 114 $8 \vworkdivides (n-k)$), although this is not required. 115 If data is stored rather than transmitted, we may assume that 116 the check bits are stored at the last addresses of ROM or EEPROM. 117 As explained in Section \ref{cedc0:scon0:scco0}, 118 in this chapter only codes where the checkbits are appended to the unmodified 119 data bits are considered. 120 121 Notationally, we treat the $n$-bit message as an ordered collection of 122 bits, represented by a row vector 123 124 125 \label{eq:cedc0:scon0:sccb0:01} 126 [m_0, m_1, \ldots{}, m_{n-1}] . 127 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 348 \label{eq:cedc0:scon0:secv0:01} 349 d_{ED} = \hat{d} - 1 . 350 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 419 \label{eq:cedc0:scon0:secv0:02} 420 \hat{d} > 2 \rho 421 422 423 \noindent{}or equivalently when considering only integers that 424 425 426 \label{eq:cedc0:scon0:secv0:03} 427 \hat{d} \geq 2 \rho + 1 . 428 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 443 \label{eq:cedc0:scon0:secv0:04} 444 d_{EC} = \rho = \left\lfloor {\frac{\hat{d}-1}{2}} \right\rfloor . 445 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 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 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 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 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 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 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 992 \label{eq:cedc0:scob0:psr0:01} 993 \mathbb{B} = \{ 0, 1 \} , 994 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 1019 \label{eq:cedc0:scob0:psr0:02} 1020 S(n, \rho ) = \left({\begin{array}{cc}n\\\rho\end{array}}\right) . 1021 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 1108 \label{eq:cedc0:scob0:rbc0:shsp0:01} 1109 2^k V(n, \rho) \leq 2^n . 1110 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 1175 \label{eq:cedc0:scon0:smgo0:01} 1176 t_{EX} = t_s + m t_d . 1177 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 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 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 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 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 1295 \label{eq:cedc0:slco0:spcm0:01} 1296 H m^T = \mathbf{0} . 1297 1298 1299 \noindent{}More explicitly, we may write (\ref{eq:cedc0:slco0:spcm0:01}) 1300 as 1301 1302 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 1313 1314 \noindent{}where of course 1315 1316 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 1325 1326 \noindent{}and 1327 1328 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 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 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 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 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 1386 1387 \noindent{}and where the parity check matrix is 1388 1389 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 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 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 1414 1415 \noindent{}and 1416 1417 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 1425 1426 Applying (\ref{eq:cedc0:slco0:spcm0:01}) yields 1427 1428 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 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 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 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 1632 \label{eq:cedc0:slco0:sgma0:01b} 1633 G_{k \times n} = [ I_{k \times k} | G'_{k \times n-k}] . 1634 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 1644 \label{eq:cedc0:slco0:sgma0:02} 1645 G' = (H')^T, 1646 1647 1648 \noindent{}or equivalently 1649 1650 1651 \label{eq:cedc0:slco0:sgma0:03} 1652 H' = (G')^T . 1653 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 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 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 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 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 2033 \label{eq:cedc0:scco0:sdpo0:a01} 2034 [m_{n-1}, m_{n-2}, \ldots{}, m_{0}] 2035 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 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 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 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 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 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 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 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 2209 2210 Adding the third row to the first row and to the second row (two 2211 row operations) yields 2212 2213 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 2224 2225 Finally, adding the fourth row to the second row and to the third row (two 2226 row operations) yields 2227 2228 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 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 2324 \label{eq:cedc0:scob0:spfc0:01} 2325 2^k V(n, \rho) = 2^n , 2326 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 $HeadURL$ 2457 $Revision$ 2458 $Date$ 2459 $Author$ 2460 \end{verbatim} 2461 \end{tiny} 2462 \noindent\rule[0.25in]{\textwidth}{1pt} 2463 \end{figure} 2464 2465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2467 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2468 % 2469 %End of file C_EDC0.TEX