Parent Directory | Revision Log

Revision **277** -
(**hide annotations**)
(**download**)
(**as text**)

*Tue Aug 13 02:35:39 2019 UTC*
(5 years ago)
by *dashley*

File MIME type: application/x-tex

File size: 107798 byte(s)

File MIME type: application/x-tex

File size: 107798 byte(s)

Change keyword substitution (migration from cvs to svn). Add quotation.

1 | dashley | 140 | %$Header$ |

2 | |||

3 | \chapter[\cedczeroshorttitle{}]{\cedczerolongtitle{}} | ||

4 | |||

5 | \label{cedc0} | ||

6 | |||

7 | \beginchapterquote{``True genius resides in the capacity for evaluation of uncertain, | ||

8 | hazardous, and conflicting information.''} | ||

9 | {Winston Churchill} | ||

10 | \index{Churchill, Winston} | ||

11 | |||

12 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

13 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

14 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

15 | \section{Introduction} | ||

16 | %Section tag: INT0 | ||

17 | \label{cedc0:sint0} | ||

18 | |||

19 | In microcontroller work, it is frequently necessary to consider how | ||

20 | best to add redundancy to data. The following design scenarios are | ||

21 | common. | ||

22 | |||

23 | \begin{enumerate} | ||

24 | \item Immediately on powerup, a microcontroller product calculates | ||

25 | the checksum of its program memory (usually ROM or FLASH) and compares this | ||

26 | checksum to a stored value in order to detect possible corruption of program | ||

27 | memory. What is the best way to calculate a checksum for this | ||

28 | purpose? | ||

29 | \item A storage medium that will tolerate a limited number of write cycles | ||

30 | (such as EEPROM), will used to used to store data which will change | ||

31 | and need to rewritten more times than the life of the medium will | ||

32 | accomodate. As a result, a strategy which wears out a portion of the medium | ||

33 | and then uses another portion is employed. When a portion of the medium | ||

34 | wears out (as evidenced by corruption of bits), how can the data be | ||

35 | reliably recovered before | ||

36 | being transferred to the next portion? | ||

37 | \item A microcontroller product stores data in battery-backed RAM while powered | ||

38 | down. What type of checksum should be added to this data to provide the maximum | ||

39 | protection against data corruption? | ||

40 | \item Microcontrollers on the same circuit board communicate with each other | ||

41 | using UARTs. What form of checksum should be used to add protection | ||

42 | against electrical noise? | ||

43 | \end{enumerate} | ||

44 | |||

45 | |||

46 | This chapter deals with the mathematical basis for four | ||

47 | questions. | ||

48 | |||

49 | \begin{enumerate} | ||

50 | \item What is the mathematical basis for redundancy to allow error | ||

51 | detection and error correction? | ||

52 | \item How can redundancy be added to data to enable detection of errors? | ||

53 | \item How can redundancy be added to data to enable correction of | ||

54 | errors? | ||

55 | \item How can adding redundancy (encoding) and detecting and correcting | ||

56 | errors (decoding) be performed efficiently in | ||

57 | microcontroller software? | ||

58 | \end{enumerate} | ||

59 | |||

60 | Note that although the results presented in this chapter for the most part | ||

61 | have their origins in the study of communication channels, the problem of | ||

62 | protecting computer storage that may degrade (disc, tape, battery-backed RAM, | ||

63 | EEPROM, etc.) is mathematically the same problem as protecting data transmitted | ||

64 | through a communication channel. In either case $k$ data bits are protected | ||

65 | by $n-k$ check bits (see Figure \ref{fig:cedc0:scon0:sccb0:01}), | ||

66 | and the essence of the mathematical problem is how best to | ||

67 | select the check bits. | ||

68 | |||

69 | |||

70 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

71 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

72 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

73 | \section{Coding Concepts} | ||

74 | %Section tag: con0 | ||

75 | \label{cedc0:scon0} | ||

76 | |||

77 | \index{coding theory}\emph{Coding theory} is the branch of mathematics | ||

78 | concerned with transmitting data across noisy channels and recovering | ||

79 | the data \cite{bibref:w:ctfirst50}. In this section we introduce the | ||

80 | basic concepts and terminology which apply to microcontroller work. | ||

81 | |||

82 | |||

83 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

84 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

85 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

86 | \subsection{Bits, Communication Channels, Messages, And Check Bits} | ||

87 | %Subection tag: ccb0 | ||

88 | \label{cedc0:scon0:sccb0} | ||

89 | |||

90 | We assume that the data we wish to transmit is an ordered sequence of \index{bit}bits. | ||

91 | Each bit is a symbol of the \index{binary alphabet}binary alphabet, | ||

92 | $\mathbb{B} = \{0,1\}$. Many results in coding theory have been generalized to | ||

93 | alphabets with more than two symbols, but for microcontroller work it is adequate | ||

94 | to consider only $\mathbb{B}$, and in this chapter only | ||

95 | $\mathbb{B}$ is considered. | ||

96 | |||

97 | Bits are transmitted through a \index{communication channel}\index{channel}% | ||

98 | \emph{communication channel} (or simply \emph{channel}), which may with probability $p$ | ||

99 | corrupt a transmitted bit from 0 to 1 or vice-versa; or with | ||

100 | probability $q=1-p$ fail to corrupt a bit. For analysis, | ||

101 | we make the simplest mathematical assumptions and assume that | ||

102 | the probability of corruption from 0 to 1 is the same as the probability | ||

103 | of corruption from 1 to 0 (i.e. $p_{0\rightarrow{}1} = p_{1\rightarrow{}0} = p$), | ||

104 | and that corruption of each bit is independent. Alternately, we may imagine that rather | ||

105 | than being potentially corrupted during transmission, each bit is potentially | ||

106 | corrupted by the degradation of computer storage. | ||

107 | |||

108 | We assume that data is transmitted in blocks of | ||

109 | $n$ bits, consisting of $k$ data bits with $n-k$ check bits | ||

110 | (redundancy bits) appended (Figure \ref{fig:cedc0:scon0:sccb0:01}). This concatenation of | ||

111 | $k$ data bits and $n-k$ check bits is called a \index{message}\emph{message}. | ||

112 | Most commonly | ||

113 | in practice, $8 \vworkdivides n,k$ (and consequently | ||

114 | $8 \vworkdivides (n-k)$), although this is not required. | ||

115 | If data is stored rather than transmitted, we may assume that | ||

116 | the check bits are stored at the last addresses of ROM or EEPROM. | ||

117 | As explained in Section \ref{cedc0:scon0:scco0}, | ||

118 | in this chapter only codes where the checkbits are appended to the unmodified | ||

119 | data bits are considered. | ||

120 | |||

121 | Notationally, we treat the $n$-bit message as an ordered collection of | ||

122 | bits, represented by a row vector | ||

123 | |||

124 | \begin{equation} | ||

125 | \label{eq:cedc0:scon0:sccb0:01} | ||

126 | [m_0, m_1, \ldots{}, m_{n-1}] . | ||

127 | \end{equation} | ||

128 | |||

129 | \noindent{}(Figure \ref{fig:cedc0:scon0:sccb0:01}, | ||

130 | includes bit notational conventions.) $m_0$ through $m_{k-1}$ are data bits, and | ||

131 | $m_k$ through $m_{n-1}$ are check bits. We may also | ||

132 | treat the vector in (\ref{eq:cedc0:scon0:sccb0:01}) as | ||

133 | the concatenation of data bits $d_0$ through $d_{k-1}$ and | ||

134 | check bits $c_0$ through $c_{n-k-1}$, in which case we use | ||

135 | either of the following notations: | ||

136 | |||

137 | \begin{eqnarray} | ||

138 | \label{eq:cedc0:scon0:sccb0:02} | ||

139 | & [d_0, d_1, \ldots{}, d_{k-1}, c_0, c_1, \ldots{}, c_{n-k-1}] , & \\ | ||

140 | \label{eq:cedc0:scon0:sccb0:02b} | ||

141 | & [d_0, d_1, \ldots{}, d_{k-1}] | [c_0, c_1, \ldots{}, c_{n-k-1}] . & | ||

142 | \end{eqnarray} | ||

143 | |||

144 | Implicit in | ||

145 | this model is the assumption that a framing error (where communication hardware or | ||

146 | software misidentifies a block of data in time) is much less probable than | ||

147 | a collection of bit errors which overwhelm the detection/correction | ||

148 | capability of the $n-k$ check bits. There are in fact some | ||

149 | scenarios\footnote{One classic example is the CAN bit-stuffing vulnerability which can | ||

150 | with some data patterns lower the Hamming distance of CAN to 2.} | ||

151 | where mechanisms exist to circumvent the function of the check bits by creating | ||

152 | framing errors. | ||

153 | By their nature, such scenarios involve the corruption of a small number of bits | ||

154 | (or samples) in a way so as to generate a framing error and shift a large number of bits | ||

155 | right or left. We assume for analytic convenience that the probability of | ||

156 | a framing error is much less than the probability of the corruption of enough bits | ||

157 | to overwhelm the capability of the check bits. However, experience has shown that | ||

158 | this assumption needs to be verified, as many practical communication protocols have | ||

159 | framing weaknesses.\footnote{Note that the notion of a framing error does not apply | ||

160 | to a medium that does not use start and end markers that might be misinterpreted. | ||

161 | For example, ROM or EEPROM have no notion of a framing error.} | ||

162 | |||

163 | \begin{figure} | ||

164 | \centering | ||

165 | \includegraphics[width=4.6in]{c_edc0/cword01.eps} | ||

166 | \caption{Message Consisting Of The Concatenation Of $k$ Data Bits And $n-k$ | ||

167 | Check Bits, With Bit Notational Conventions} | ||

168 | \label{fig:cedc0:scon0:sccb0:01} | ||

169 | \end{figure} | ||

170 | |||

171 | We have referred to \emph{check bits} without describing the ways in which they | ||

172 | might be calculated. We use the term \index{checksum}\emph{checksum} to refer | ||

173 | to the contiguous group of $n-k$ check bits; whether or not the bits are calculated | ||

174 | through summation. In general, we impose only the requirement that the $n-k$-bit | ||

175 | checksum is a deterministic function of the $k$ data bits. | ||

176 | |||

177 | We often refer to a message or a portion of a message as a | ||

178 | \index{vector}\emph{vector}. This nomenclature is appropriate because it is | ||

179 | convenient to treat a message as a row vector of bits. | ||

180 | An 80-bit message might | ||

181 | be viewed as a $1 \times 80$ matrix (i.e. a row vector) with each matrix element | ||

182 | $\in \mathbb{B}$. We use \emph{message} and \emph{vector} somewhat interchangeably. | ||

183 | |||

184 | We define the \index{weight}\emph{weight} of a message or vector as the number of | ||

185 | 1's in the message or vector. We denote the weight of a vector or message $v$ as | ||

186 | $wt(v)$. | ||

187 | |||

188 | |||

189 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

190 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

191 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

192 | \subsection[Codewords, Codes, And \protect\mbox{\protect$(n,k)$} Block Codes] | ||

193 | {Codewords, Codes And \protect\mbox{\protect\boldmath$(n,k)$} Block Codes} | ||

194 | %Subection tag: cco0 | ||

195 | \label{cedc0:scon0:scco0} | ||

196 | |||

197 | A \index{codeword}\emph{codeword} (as we define it here) is a message in which | ||

198 | the $n-k$ check bits are consistent with the $k$ data bits. | ||

199 | Under this definition, all codewords are messages, but not all possible messages | ||

200 | are codewords. | ||

201 | |||

202 | A common cognitive misconception is that it matters in transmission or | ||

203 | storage whether the $k$ data bits or the $n-k$ check bits are corrupted. | ||

204 | It matters not. We seek mathematical properties that apply to the messages | ||

205 | and codewords, not to the $k$ data bits or $n-k$ check bits separately. | ||

206 | |||

207 | In the most general terms, a \index{code}\emph{code} is \emph{any} system | ||

208 | of information representation for transmission, not necessarily requiring | ||

209 | transmission in fixed-length blocks. However, in this discussion, by | ||

210 | \emph{code} we mean the set of all bit | ||

211 | patterns with data and check bits consistent (i.e. all codewords) | ||

212 | which can be transmitted over a communication channel or stored | ||

213 | in computer memory. For example, | ||

214 | $\{000, 011, 101, 110\}$ is a code. | ||

215 | |||

216 | A code may be specified either by enumeration or by rule. For example, | ||

217 | we might also specify the code of the previous paragraph as | ||

218 | $\{ABC: C=A \oplus B\}$. With larger codes, enumeration is naturally not practical and | ||

219 | also not necessary to study the properties of interest. | ||

220 | |||

221 | An | ||

222 | \index{(n,k) block code@$(n,k)$ block code}\index{n,k block code@$(n,k)$ block code}% | ||

223 | $(n,k)$ \emph{block code} is a code where $n$ bits are transmitted (or stored) at a | ||

224 | time, and characterized by a function which maps from $k$ data bits to $n$ bits which | ||

225 | are transmitted (or stored). | ||

226 | |||

227 | In a general $(n,k)$ block code, the $n$ transmitted | ||

228 | bits are not required to contain or resemble the $k$ data bits; and if the $k$ data bits | ||

229 | are contained they are not required to have a specific order or placement within | ||

230 | the $n$ transmitted bits. Because we are interested in adding | ||

231 | redundancy to ROM and in other applications | ||

232 | where the stored data must be contiguous and unmodified, we confine ourselves | ||

233 | to $(n,k)$ block codes as depicted in Figure | ||

234 | \ref{fig:cedc0:scon0:sccb0:01}, where the $k$ data bits are contiguous, unchanged, | ||

235 | in their original order, and prepended to the $n-k$ check bits. | ||

236 | |||

237 | |||

238 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

239 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

240 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

241 | \subsection{Hamming Distance, Minimum Hamming Distance, And Errors} | ||

242 | %Subection tag: mhd0 | ||

243 | \label{cedc0:scon0:smhd0} | ||

244 | |||

245 | We define the \index{Hamming distance}\emph{Hamming distance} between | ||

246 | two same-length blocks $c$ and $d$, denoted $d(c,d)$, as the number of bit positions | ||

247 | in which the blocks differ. Note that $d(c,d)$ is necessarily the same as the number | ||

248 | of 1's in $c \oplus d$. Note also that $d(c,d)$ is the weight of the | ||

249 | exclusive-OR of $c$ and $d$, i.e. $d(c,d) = wt(c \oplus d)$. (We discuss the properties | ||

250 | of the exclusive-OR function later in Section \ref{cedc0:sfft0:dff0}.) | ||

251 | |||

252 | We define the \index{minimum Hamming distance}\emph{minimum Hamming distance} | ||

253 | of a code, denoted $\hat{d}$, as the smallest Hamming distance between any two | ||

254 | members of the code. For example, the minimum Hamming distance of | ||

255 | $\{000, 011, 101, 110\}$, | ||

256 | denoted $\hat{d}(\{000, 011, 101, 110\})$, | ||

257 | is 2, and the minimum Hamming distance of | ||

258 | $\{0001, 0110, 1010, 1101\}$, | ||

259 | denoted $\hat{d}(\{0001, 0110, 1010, 1101\})$, | ||

260 | is also 2.\footnote{See Exercise | ||

261 | \ref{exe:cedc0:sexe0:01}.} | ||

262 | |||

263 | We define an \index{error}\emph{error} (or alternatively, a | ||

264 | \emph{bit corruption} or simply a \emph{corruption}) as the corruption | ||

265 | of a transmitted or stored | ||

266 | bit from 0 to 1 or from 1 to 0. As mentioned in | ||

267 | Section \ref{cedc0:scon0:sccb0}, we assume that a corruption may occur | ||

268 | with probability $p$ or fail to occur with probability $q=1-p$. | ||

269 | |||

270 | We define a \index{message corruption}\emph{message corruption} or simply | ||

271 | \emph{corruption} as the corruption of one or more bits within the message | ||

272 | during transmission or storage. | ||

273 | Note that the minimum Hamming distance $\hat{d}$ of a code | ||

274 | guarantees that at least $\hat{d}$ errors are required to transform | ||

275 | one codeword into another, thus guaranteeing that any corruption | ||

276 | of $\hat{d}-1$ or fewer bits is detectable. | ||

277 | |||

278 | If the errors within a message are distributed in a special way, we may be | ||

279 | able to devise codes that are more resistant to these special distributions | ||

280 | than to an arbitrary distribution of errors. One such special distribution | ||

281 | is a \index{burst error}\emph{burst error}. A \emph{burst error of length $b$} | ||

282 | is defined as any number of errors in a span of $b$ bits. For example, corruption of | ||

283 | 00001111 to 00011001 represents a burst error of length 4 (the corruptions are in | ||

284 | the 4th, 6th, and 7th bits, which span 4 bits inclusive). A burst error may naturally | ||

285 | span no fewer than 1 bit and no more than $n$ bits. | ||

286 | |||

287 | We are very careful \emph{not} to define a codeword as an | ||

288 | uncorrupted message. No code except a code consisting of only one codeword | ||

289 | can sustain an unlimited number of bit corruptions while still guaranteeing | ||

290 | that the message corruption will be detectable.\footnote{This observation that | ||

291 | a single-codeword code can sustain an unlimited number of bit corruptions is a | ||

292 | mathematical fallacy and a semantic parlor trick. An $(n,k)$ block code with only | ||

293 | one code word effectively has a maximum Hamming distance $\hat{d}$ of $n$ plus the number | ||

294 | of framing bits, stop bits, etc. in the message as transmitted. Sufficient noise | ||

295 | in a communication channel may cause communication hardware to believe the | ||

296 | codeword was transmitted when in fact it was not. See the remarks regarding | ||

297 | framing weaknesses in Section \ref{cedc0:scon0:sccb0}.} A codeword may in fact | ||

298 | be a corrupted message where the number of bit corruptions has overwhelmed the | ||

299 | minimum Hamming distance $\hat{d}$ of the code so as to transform one codeword | ||

300 | into another. | ||

301 | |||

302 | Generally, error-detecting and error-correcting codes | ||

303 | (Section \ref{cedc0:scon0:secv0}) must be selected with some knowledge | ||

304 | of the error | ||

305 | rates of the | ||

306 | communication channel or storage medium. Noisier communication channels | ||

307 | or poorer storage mediums require codes with | ||

308 | better error-detecting and/or error-correcting properties. Normally, the design goal | ||

309 | is to achieve a very low probability of undetected corruption or uncorrectable corruption. | ||

310 | |||

311 | |||

312 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

313 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

314 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

315 | \subsection{Error-Detecting Versus Error-Correcting Codes} | ||

316 | %Subection tag: ecv0 | ||

317 | \label{cedc0:scon0:secv0} | ||

318 | |||

319 | An \index{error-detecting code}\emph{error-detecting code} is a code which is | ||

320 | designed so that message errors | ||

321 | (a message which is not a codeword) will be detected but not corrected. | ||

322 | Error-detecting codes are attractive | ||

323 | when there is the opportunity to request that the transmitter retransmit the | ||

324 | corrupted data, or when obtaining a correct copy of the data is not important but | ||

325 | detecting (and perhaps discarding) corrupted data is important. | ||

326 | |||

327 | An \index{error-correcting code}\emph{error-correcting code} is a code designed | ||

328 | so that message errors can be both detected and corrected. Error-correcting | ||

329 | codes are attractive when | ||

330 | there is no opportunity for retransmission of the corrupted data, but possessing | ||

331 | a correct copy of the data is important. Example attractive | ||

332 | applications of error-correcting codes are compact disc audio data (where the | ||

333 | CD should play even with scratches, and there is no opportunity to obtain | ||

334 | retransmission of the data) and data transmitted from space exploration satellites | ||

335 | (where the signal-to-noise ratio is low, and there is not opportunity for retransmission | ||

336 | or perhaps not even two-way communication). | ||

337 | |||

338 | In this section we show the required relationship between minimum Hamming | ||

339 | distance $\hat{d}$ and the error-detecting and error-correcting capabilities | ||

340 | of a code. | ||

341 | |||

342 | We define the \index{error-detecting capability of a code}\index{code!error-detecting capability}% | ||

343 | \emph{error-detecting capability} $d_{ED}$ of a code as the largest number of bit errors | ||

344 | in a message which will \emph{always} be detectable. It follows | ||

345 | immediately and intuitively that | ||

346 | |||

347 | \begin{equation} | ||

348 | \label{eq:cedc0:scon0:secv0:01} | ||

349 | d_{ED} = \hat{d} - 1 . | ||

350 | \end{equation} | ||

351 | |||

352 | \noindent{}If the minimum | ||

353 | Hamming distance of a code is $\hat{d}$, then there exists at least | ||

354 | one pair of codewords | ||

355 | $c_1, c_2$ such that $d(c_1, c_2) = \hat{d}$. Thus it is possible to corrupt | ||

356 | $c_1$ into $c_2$ with $\hat{d}$ corrupted bits and therefore | ||

357 | $d_{ED} < \hat{d}$. On the other hand, the minimum Hamming distance | ||

358 | $\hat{d}$ guarantees that it is \emph{not} possible to corrupt from one codeword to another | ||

359 | with only $\hat{d}-1$ bit corruptions. Therefore | ||

360 | (\ref{eq:cedc0:scon0:secv0:01}) is true. | ||

361 | |||

362 | We define the \index{error correcting capability of a code}\index{code!error correcting capability}% | ||

363 | \emph{error correcting capability} $d_{EC}$ of a code as the largest number of bit errors | ||

364 | in a message which will \emph{always} be correctable. By \emph{correctable} we mean | ||

365 | that we can recover the original $n$-bit codeword into which errors were introduced. | ||

366 | |||

367 | To illustrate the relationship between Hamming distance and the error correcting | ||

368 | capability of a code, consider the code $\{000, 111\}$ depicted in | ||

369 | Figure \ref{fig:cedc0:scon0:secv0:01}. In the figure, each edge in the cube depicts | ||

370 | a single bit error which may occur in a message. Each vertex in the cube | ||

371 | represents a message. | ||

372 | |||

373 | \begin{figure} | ||

374 | \centering | ||

375 | \includegraphics[height=2.5in]{c_edc0/cube01.eps} | ||

376 | \caption{Three-Dimensional Cube Illustrating Error Correction With Code $\{000, 111\}$} | ||

377 | \label{fig:cedc0:scon0:secv0:01} | ||

378 | \end{figure} | ||

379 | |||

380 | Note that the minimum Hamming $\hat{d}$ distance of the code $\{000, 111\}$ is 3: in | ||

381 | Figure \ref{fig:cedc0:scon0:secv0:01} one must travel along three edges | ||

382 | (corresponding to three bit errors) in order to travel from 000 to 111 or back. | ||

383 | |||

384 | If we claim that a code has an error correcting capability of $d_{EC}$, | ||

385 | then any corruption of a codeword by $d_{EC}$ errors must be correctable. | ||

386 | To be \emph{correctable} means that if we guess based on the corrupted | ||

387 | codeword what the original codeword is, we must always be able to guess | ||

388 | correctly. This notion implies that the original codeword must be the | ||

389 | closest codeword (as measured by number of bit corruptions) to the corrupted codeword. | ||

390 | |||

391 | This notion of \emph{closest} codeword leads to the notion of a \emph{packing sphere}. | ||

392 | A \emph{packing sphere of radius $\rho$} is the set of all messages | ||

393 | at a distance of $\rho$ or less from a given codeword. In order for | ||

394 | a code to have an error correcting capability of $d_{EC}=\rho$, | ||

395 | the packing spheres or radius $\rho$ about all codewords must be disjoint. | ||

396 | This ensures that any message at a distance $d_{EC}$ or less from a codeword | ||

397 | does, in fact, have a \emph{nearest} codeword. | ||

398 | |||

399 | Figure \ref{fig:cedc0:scon0:secv0:02} is | ||

400 | Figure \ref{fig:cedc0:scon0:secv0:01} redrawn to show the packing spheres of | ||

401 | radius $\rho=1$ about the two codewords 000 and 111. The code | ||

402 | $\{000,111\}$ depicted in Figures \ref{fig:cedc0:scon0:secv0:01} and | ||

403 | \ref{fig:cedc0:scon0:secv0:02} has an error correcting capability of | ||

404 | $d_{EC}=1$. For error correction, any message in the packing sphere | ||

405 | about 000 must be mapped back to 000, and any message in the packing sphere | ||

406 | about 111 must be transformed back to 111. | ||

407 | |||

408 | \begin{figure} | ||

409 | \centering | ||

410 | \includegraphics[height=2.5in]{c_edc0/cube02.eps} | ||

411 | \caption{Packing Spheres Of Radius $\rho{}=1$ About Codewords 000 And 111} | ||

412 | \label{fig:cedc0:scon0:secv0:02} | ||

413 | \end{figure} | ||

414 | |||

415 | The requirement for disjointness of packing spheres immediately leads to | ||

416 | the constraint | ||

417 | |||

418 | \begin{equation} | ||

419 | \label{eq:cedc0:scon0:secv0:02} | ||

420 | \hat{d} > 2 \rho | ||

421 | \end{equation} | ||

422 | |||

423 | \noindent{}or equivalently when considering only integers that | ||

424 | |||

425 | \begin{equation} | ||

426 | \label{eq:cedc0:scon0:secv0:03} | ||

427 | \hat{d} \geq 2 \rho + 1 . | ||

428 | \end{equation} | ||

429 | |||

430 | \noindent{}Since the radius $\rho$ of the packing sphere is | ||

431 | equivalent to the error correcting capability $d_{EC}$ of | ||

432 | a code, we may equivalently write | ||

433 | (\ref{eq:cedc0:scon0:secv0:02}) and (\ref{eq:cedc0:scon0:secv0:03}) | ||

434 | as $\hat{d} > 2 d_{EC}$ and $\hat{d} \geq 2 d_{EC} + 1$, respectively. | ||

435 | |||

436 | (\ref{eq:cedc0:scon0:secv0:02}) and (\ref{eq:cedc0:scon0:secv0:03}) | ||

437 | treat minimum Hamming distance $\hat{d}$ as a function of | ||

438 | the packing sphere radius $\rho$. With a known minimum Hamming distance | ||

439 | $\hat{d}$, one may also calculate the largest disjoint | ||

440 | packing spheres that can be constructed: | ||

441 | |||

442 | \begin{equation} | ||

443 | \label{eq:cedc0:scon0:secv0:04} | ||

444 | d_{EC} = \rho = \left\lfloor {\frac{\hat{d}-1}{2}} \right\rfloor . | ||

445 | \end{equation} | ||

446 | |||

447 | This section has demonstrated the relationship between the minimum Hamming | ||

448 | distance $\hat{d}$ of a code and the error detection capability of the code | ||

449 | (Equation \ref{eq:cedc0:scon0:secv0:01}), as well as the relationship between the | ||

450 | minimum Hamming | ||

451 | distance $\hat{d}$ and the error correction capabilility | ||

452 | (Equations \ref{eq:cedc0:scon0:secv0:02} through | ||

453 | \ref{eq:cedc0:scon0:secv0:04}). | ||

454 | |||

455 | Note that the relationships derived do apply to the example presented in | ||

456 | Figures \ref{fig:cedc0:scon0:secv0:01} and \ref{fig:cedc0:scon0:secv0:02}. | ||

457 | The code shown in the figures has a minimum Hamming distance $\hat{d}=3$. | ||

458 | (\ref{eq:cedc0:scon0:secv0:01}) predicts that this code should have | ||

459 | an error detection capability of $d_{ED}=2$, which is the case. | ||

460 | (\ref{eq:cedc0:scon0:secv0:04}) predicts that this code should have an error correction | ||

461 | capability $d_{EC}=1$, which is also the case and can be verified by | ||

462 | examining Figure \ref{fig:cedc0:scon0:secv0:02}. | ||

463 | |||

464 | In the code presented in Figures \ref{fig:cedc0:scon0:secv0:01} and | ||

465 | \ref{fig:cedc0:scon0:secv0:02}, the union of all packing spheres of radius | ||

466 | $\rho=1$ contains all messages (i.e. there are no messages which are not part of | ||

467 | a packing sphere). Such a code is called a \emph{perfect code}. Most codes | ||

468 | are not perfect codes, and this will be discussed later. | ||

469 | |||

470 | |||

471 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

472 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

473 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

474 | \section[Finite Field Theory Applied To \protect\mbox{\protect$\mathbb{B}$}] | ||

475 | {Finite Field Theory Applied To \protect\mbox{\protect\boldmath$\mathbb{B}$}} | ||

476 | %Section tag: fft0 | ||

477 | \label{cedc0:sfft0} | ||

478 | |||

479 | This | ||

480 | section deals with \index{finite field}finite field | ||

481 | theory as applied to the binary alphabet, | ||

482 | $\mathbb{B} = \{ 0, 1 \}$. | ||

483 | This section is one of two sections in this chapter which deal with | ||

484 | \index{finite field}finite field theory | ||

485 | (the other section is Section \ref{cedc0:sfft1}, | ||

486 | which deals with finite field theory as applied to polynomials). | ||

487 | |||

488 | |||

489 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

490 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

491 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

492 | \subsection{\emph{Why} Field Theory?} | ||

493 | %Subection tag: wft0 | ||

494 | \label{cedc0:sfft0:wft0} | ||

495 | |||

496 | The most important question to answer immediately (for engineers, anyway) | ||

497 | is \emph{why} field theory is necessary at all. The answer is that | ||

498 | there are two general approaches that can be used to approach coding | ||

499 | theory: | ||

500 | |||

501 | \begin{enumerate} | ||

502 | \item \emph{Combinational:} | ||

503 | approaching the problem by considering combinations and | ||

504 | permutations (see Section \ref{cedc0:scob0}, for example). This approach | ||

505 | can give some insight and produce useful bounds, but in general it is hard | ||

506 | to approach the problem of generating codes with an arbitrarily large minimum | ||

507 | Hamming distance $\hat{d}$ using a purely combinational approach. | ||

508 | \item \emph{Field Theory:} approaching the problem by attempting to add algebraic | ||

509 | structure to codes. This approach leads to classes of solutions that | ||

510 | are unavailable using purely combinational approaches. To add | ||

511 | \emph{algebraic structure} means to define operations so as to add useful | ||

512 | algebraic properties that facilitate higher-level inferences | ||

513 | and abstractions. For example, | ||

514 | algebraic structure is ultimately what allows us to define the rank | ||

515 | of a matrix with elements $\in \mathbb{B}$ in the same way we do with | ||

516 | matrices with elements $\in \vworkrealset$. | ||

517 | \end{enumerate} | ||

518 | |||

519 | Note that combinational and field theory approaches are complementary: each | ||

520 | approach gives some unique insight and solutions that the other approach cannot | ||

521 | provide. | ||

522 | |||

523 | Field theory is necessary in order to derive a framework in which to | ||

524 | systematically generate codes with a large minimum Hamming distance $\hat{d}$. | ||

525 | |||

526 | |||

527 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

528 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

529 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

530 | \subsection{Definition Of A Finite Field} | ||

531 | %Subection tag: dff0 | ||

532 | \label{cedc0:sfft0:dff0} | ||

533 | |||

534 | We first define what a \index{finite field} \emph{finite field} is in general, and | ||

535 | then we show how this definition is applied to $\mathbb{B} = \{ 0, 1 \}$. | ||

536 | |||

537 | \begin{vworkdefinitionstatementpar}{Finite Field} | ||

538 | A \emph{finite field} \cite{bibref:w:weissteinmathworld} | ||

539 | is a finite set of elements (the cardinality of this | ||

540 | set is called the \index{field order}\emph{field order}) which | ||

541 | satisfies the field axioms | ||

542 | listed in Table \ref{tbl:cedc0:sfft0:dff0:01} for both addition and | ||

543 | multiplication. | ||

544 | |||

545 | \begin{table} | ||

546 | \caption{Field Axioms For A Finite Field (From \cite{bibref:w:weissteinmathworld})} | ||

547 | \label{tbl:cedc0:sfft0:dff0:01} | ||

548 | \begin{center} | ||

549 | \begin{tabular}{|l|c|c|} | ||

550 | \hline | ||

551 | Name & Addition & Multiplication \\ | ||

552 | \hline | ||

553 | \hline | ||

554 | Commutativity & $a+b = b+a$ & $ab = ba$ \\ | ||

555 | \hline | ||

556 | Associativity & $(a+b)+c=a+(b+c)$ & $(ab)c=a(bc)$ \\ | ||

557 | \hline | ||

558 | Distributivity & $a(b+c)=ab+ac$ & $(a+b)c=ac+bc$ \\ | ||

559 | \hline | ||

560 | Identity & $a+0=a=0+a$ & $a \cdot 1=a=1 \cdot a$ \\ | ||

561 | \hline | ||

562 | Inverses & $a+(-a)=0=(-a)+a$ & $aa^{-1}=1=a^{-1}a$ if $a \neq 0$ \\ | ||

563 | \hline | ||

564 | \end{tabular} | ||

565 | \end{center} | ||

566 | \end{table} | ||

567 | |||

568 | Such a field is also called a \index{Galois field}\emph{Galois field}. | ||

569 | In this chapter, we are concerned with the Galois field containing | ||

570 | only two elements ($\mathbb{B}=\{ 0,1 \}$), and this field is denoted $GF(2)$. | ||

571 | \end{vworkdefinitionstatementpar} | ||

572 | \vworkdefinitionfooter{} | ||

573 | |||

574 | The study of fields is a topic from \index{abstract algebra}\emph{abstract algebra}, | ||

575 | a branch of mathematics. This chapter provides only the | ||

576 | minimum amount of information about finite field theory to explain | ||

577 | the presented application, and so there are many mathematical results | ||

578 | not discussed. | ||

579 | |||

580 | The definition of a finite field (Definition \ref{tbl:cedc0:sfft0:dff0:01}) | ||

581 | does not specify how addition and multiplication are defined---it only | ||

582 | specifies what properties must be met by whatever choice is made. | ||

583 | We now present the only possible choices for addition, multiplication, | ||

584 | formation of the additive inverse, and formation of the multiplicative inverse | ||

585 | for the elements of $\mathbb{B}=\{ 0,1 \}$. | ||

586 | |||

587 | Addition (Table \ref{tbl:cedc0:sfft0:dff0:02}) is performed modulo 2, and is | ||

588 | identical to the exclusive-OR | ||

589 | function. In computer software, this function is normally implemented using | ||

590 | the XOR machine instruction, which operates on many bits in parallel. Although | ||

591 | we would be justified in using `$+$' to denote this operation, instead we | ||

592 | use `$\oplus$' because it corresponds more closely to the machine instruction | ||

593 | actually used to implement this binary operation. | ||

594 | |||

595 | \begin{table} | ||

596 | \caption{Truth Table Of Addition Over $\mathbb{B}=\{ 0,1 \}$ (Denoted $\oplus$)} | ||

597 | \label{tbl:cedc0:sfft0:dff0:02} | ||

598 | \begin{center} | ||

599 | \begin{tabular}{|c|c|c|} | ||

600 | \hline | ||

601 | $a$ & $b$ & $c = a \oplus b$ \\ | ||

602 | \hline | ||

603 | \hline | ||

604 | 0 & 0 & 0 \\ | ||

605 | \hline | ||

606 | 0 & 1 & 1 \\ | ||

607 | \hline | ||

608 | 1 & 0 & 1 \\ | ||

609 | \hline | ||

610 | 1 & 1 & 0 \\ | ||

611 | \hline | ||

612 | \end{tabular} | ||

613 | \end{center} | ||

614 | \end{table} | ||

615 | |||

616 | Subtraction is equivalent to adding the additive inverse. | ||

617 | Table \ref{tbl:cedc0:sfft0:dff0:03} provides the | ||

618 | additive inverses of the field elements 0 and 1. Table | ||

619 | \ref{tbl:cedc0:sfft0:dff0:04} is the truth table for subtraction. | ||

620 | |||

621 | \begin{table} | ||

622 | \caption{Truth Table Of Additive Inverse Over $\mathbb{B}=\{ 0,1 \}$} | ||

623 | \label{tbl:cedc0:sfft0:dff0:03} | ||

624 | \begin{center} | ||

625 | \begin{tabular}{|c|c|} | ||

626 | \hline | ||

627 | $a$ & $-a$ \\ | ||

628 | \hline | ||

629 | \hline | ||

630 | 0 & 0 \\ | ||

631 | \hline | ||

632 | 1 & 1 \\ | ||

633 | \hline | ||

634 | \end{tabular} | ||

635 | \end{center} | ||

636 | \end{table} | ||

637 | |||

638 | \begin{table} | ||

639 | \caption{Truth Table Of Subtraction Over $\mathbb{B}=\{ 0,1 \}$ (Denoted $-$)} | ||

640 | \label{tbl:cedc0:sfft0:dff0:04} | ||

641 | \begin{center} | ||

642 | \begin{tabular}{|c|c|c|} | ||

643 | \hline | ||

644 | $a$ & $b$ & $c = a - b = a + (-b)$ \\ | ||

645 | \hline | ||

646 | \hline | ||

647 | 0 & 0 & 0 \\ | ||

648 | \hline | ||

649 | 0 & 1 & 1 \\ | ||

650 | \hline | ||

651 | 1 & 0 & 1 \\ | ||

652 | \hline | ||

653 | 1 & 1 & 0 \\ | ||

654 | \hline | ||

655 | \end{tabular} | ||

656 | \end{center} | ||

657 | \end{table} | ||

658 | |||

659 | |||

660 | Table \ref{tbl:cedc0:sfft0:dff0:05} supplies the definition of the | ||

661 | multiplication operation in $GF(2)$. | ||

662 | |||

663 | \begin{table} | ||

664 | \caption{Truth Table Of Multiplication Over $\mathbb{B}=\{ 0,1 \}$} | ||

665 | \label{tbl:cedc0:sfft0:dff0:05} | ||

666 | \begin{center} | ||

667 | \begin{tabular}{|c|c|c|} | ||

668 | \hline | ||

669 | $a$ & $b$ & $c = a b$ \\ | ||

670 | \hline | ||

671 | \hline | ||

672 | 0 & 0 & 0 \\ | ||

673 | \hline | ||

674 | 0 & 1 & 0 \\ | ||

675 | \hline | ||

676 | 1 & 0 & 0 \\ | ||

677 | \hline | ||

678 | 1 & 1 & 1 \\ | ||

679 | \hline | ||

680 | \end{tabular} | ||

681 | \end{center} | ||

682 | \end{table} | ||

683 | |||

684 | Table \ref{tbl:cedc0:sfft0:dff0:06} supplies the definition of the | ||

685 | multiplicative inverse over $GF(2)$. Note that division is assumed | ||

686 | to be the same as multiplication by the multiplicative inverse. | ||

687 | As required by the definition of a field, division by 0 is not | ||

688 | defined. | ||

689 | |||

690 | \begin{table} | ||

691 | \caption{Truth Table Of Multiplicative Inverse Over $\mathbb{B}=\{ 0,1 \}$} | ||

692 | \label{tbl:cedc0:sfft0:dff0:06} | ||

693 | \begin{center} | ||

694 | \begin{tabular}{|c|c|} | ||

695 | \hline | ||

696 | $a$ & $a^{-1}$ \\ | ||

697 | \hline | ||

698 | \hline | ||

699 | 0 & Undefined \\ | ||

700 | \hline | ||

701 | 1 & 1 \\ | ||

702 | \hline | ||

703 | \end{tabular} | ||

704 | \end{center} | ||

705 | \end{table} | ||

706 | |||

707 | There are unique properites of calculations within | ||

708 | $GF(2)$. We summarize these unique properties here. | ||

709 | |||

710 | \begin{enumerate} | ||

711 | \item \label{prop:enum:cedc0:sfft0:dff0:01:01} | ||

712 | Addition and subtraction | ||

713 | are identical. This means that we can always replace `$-$' with `$\oplus$', | ||

714 | and it also means we can break the usual rules of algebra and simply | ||

715 | ``drag'' terms joined by `$\oplus$' from one side of an equality to the other. | ||

716 | Specifically, | ||

717 | |||

718 | \begin{equation} | ||

719 | \label{eq:cedc0:sfft0:dff0:01} | ||

720 | (a = b \oplus c) \vworkequiv (a \oplus b = c) \vworkequiv (a \oplus b \oplus c = 0) . | ||

721 | \end{equation} | ||

722 | |||

723 | \item \label{prop:enum:cedc0:sfft0:dff0:01:02} | ||

724 | Adding any value to itself | ||

725 | yields $0$. This comes directly because $0 \oplus 0 = 1 \oplus 1=0$. | ||

726 | This allows the removal of pairs of identical values joined by | ||

727 | $\oplus$, i.e. | ||

728 | |||

729 | \begin{equation} | ||

730 | \label{eq:cedc0:sfft0:dff0:02} | ||

731 | 1 \oplus 1 \oplus a \oplus b \oplus a \oplus b \oplus a \oplus b \oplus a = b. | ||

732 | \end{equation} | ||

733 | \end{enumerate} | ||

734 | |||

735 | |||

736 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

737 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

738 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

739 | \subsection[Properties Of Matrices Consisting Of Elements \mbox{\protect$\in \mathbb{B}$}] | ||

740 | {Properties Of Matrices Consisting Of Elements \mbox{\protect\boldmath$\in \mathbb{B}$}} | ||

741 | %Subection tag: rmc0 | ||

742 | \label{cedc0:sfft0:rmc0} | ||

743 | |||

744 | In high school and college, most engineers studied linear algebra using | ||

745 | matrices with elements $\in \vworkrealset$. The set of real numbers combined | ||

746 | with the traditional addition and multiplication operators is | ||

747 | an \emph{infinite} field, whereas the set $\mathbb{B} = \{ 0, 1 \}$ combined | ||

748 | with the addition and multiplication operators as defined in | ||

749 | Section \ref{cedc0:sfft0:dff0} is a \emph{finite} field, namely | ||

750 | $GF(2)$. It may not be clear to a practicing engineer whether the traditional notions | ||

751 | from linear algebra apply to the finite field $GF(2)$ as | ||

752 | defined here. | ||

753 | |||

754 | It ends up that all of the traditional notions from linear algebra | ||

755 | \emph{do} apply to finite fields and to $GF(2)$. Most undergraduate linear | ||

756 | algebra texts, however, do not develop this. By | ||

757 | \emph{traditional notions} we mean: | ||

758 | |||

759 | \begin{itemize} | ||

760 | \item The notion of the rank of a matrix. | ||

761 | \item The notion of the determinant of a matrix (denoted $|A|$ or $det(A)$). | ||

762 | \item The equivalence of all of the following statements: | ||

763 | \begin{itemize} | ||

764 | \item $|A_{n \times n}| = 0$. | ||

765 | \item $A$ is not of full rank. | ||

766 | \item Any linear combination of the rows or columns of $A$ can span | ||

767 | only a subspace of $\mathbb{B}^n$. | ||

768 | \end{itemize} | ||

769 | \end{itemize} | ||

770 | |||

771 | The notion of subspace, however, has a subtly different flavor with a finite | ||

772 | field because such a subspace has a finite and countable number of elements. | ||

773 | With that in mind, we present the following lemma. | ||

774 | |||

775 | \begin{vworklemmastatement} | ||

776 | \label{lem:cedc0:sfft0:rmc0:01} | ||

777 | Linear combinations of the | ||

778 | rows or columns from an | ||

779 | $m \times n$ matrix $A$ with elements from $\mathbb{B}$ and with | ||

780 | rank $r$ can span exactly $2^r$ vectors. | ||

781 | \end{vworklemmastatement} | ||

782 | \begin{vworklemmaproof} | ||

783 | For simplicity assume a square matrix $A_{n \times n}$ with rank | ||

784 | $r \leq n$ (the result applies also to non-square matrices and to | ||

785 | the columns as well as the rows). | ||

786 | Denote the rows of $A$ as $r_0 \ldots r_{n-1}$. | ||

787 | Sort the rows of the matrix so that $r_0 \ldots{} r_{r-1}$ are linearly | ||

788 | independent and rows $r_{r} \ldots{} r_{n-1}$ are each linear combinations | ||

789 | of $r_0 \ldots{} r_{r-1}$. | ||

790 | |||

791 | Consider the $2^n$ linear combinations of the | ||

792 | $n$ rows, with each linear combination of the | ||

793 | form $\alpha_0 r_0 + \alpha_1 r_1 + \ldots{} + \alpha_{n-1} r_{n-1}$, | ||

794 | where $\alpha_i \in \mathbb{B}$. For those linear combinations | ||

795 | where there are nonzero $\alpha_{r} \ldots{} \alpha_{n-1}$, since | ||

796 | each $r_{r} \ldots{} r_{n-1}$ is a linear combination of | ||

797 | $r_0 \ldots{} r_{r-1}$, a substitution can be made to express the | ||

798 | linear combination as a sum of $r_0 \ldots{} r_{r-1}$ only, and then | ||

799 | superfluous terms can be removed in pairs | ||

800 | (Property \ref{prop:enum:cedc0:sfft0:dff0:01:02}, p. \pageref{prop:enum:cedc0:sfft0:dff0:01:02}) | ||

801 | to give a linear combination of $r_0 \ldots{} r_{r-1}$ only. | ||

802 | Thus, every $\alpha_0 r_0 + \alpha_1 r_1 + \ldots{} + \alpha_{n-1} r_{n-1}$ | ||

803 | can be simplified to $\alpha_0 r_0 + \alpha_1 r_1 + \ldots{} + \alpha_{r-1} r_{r-1}$. | ||

804 | Since no row $r_0 \ldots r_{r-1}$ is a linear combination of other rows | ||

805 | $r_0 \ldots r_{r-1}$, each of the $2^r$ linear combinations | ||

806 | is unique and thus all linear combinations of the rows | ||

807 | sum to one of $2^r$ distinct $1 \times n$ vector values. | ||

808 | \end{vworklemmaproof} | ||

809 | \vworklemmafooter{} | ||

810 | |||

811 | The ability to directly apply concepts from linear algebra to matrices | ||

812 | with elements $\in \mathbb{B}$ is in fact the reason for employing finite field | ||

813 | theory. We illustrate the applicability of standard linear algebra concepts to these | ||

814 | types of matrices with the following example. | ||

815 | |||

816 | \begin{vworkexamplestatement} | ||

817 | \label{ex:cedc0:sfft0:rmc0:01} | ||

818 | Consider the two matrices $A$ and $B$ with elements $\in \mathbb{B}$: | ||

819 | |||

820 | \begin{equation} | ||

821 | \label{eq:cedc0:sfft0:rmc0:01} | ||

822 | A = \left[\begin{array}{ccc}1&1&0\\0&1&1\\1&0&1\end{array}\right], \;\; | ||

823 | B = \left[\begin{array}{ccc}1&1&0\\0&1&1\\0&0&1\end{array}\right]. | ||

824 | \end{equation} | ||

825 | |||

826 | Determine the rank of $A$ and $B$ and the set of $1 \times 3$ vectors | ||

827 | which is spanned by linear combination of their rows. | ||

828 | \end{vworkexamplestatement} | ||

829 | \begin{vworkexampleparsection}{Solution} | ||

830 | Recall that for a $3 \times 3$ matrix | ||

831 | $\left[\begin{array}{ccc}a&b&c\\d&e&f\\g&h&i\end{array}\right]$, | ||

832 | the determinant is given by | ||

833 | $a(ei-hf) - b(di-gf) + c(dh - ge)$. However, with | ||

834 | elements from $GF(2)$, addition and subtraction are the same | ||

835 | operation (Property \ref{prop:enum:cedc0:sfft0:dff0:01:01}, p. \pageref{prop:enum:cedc0:sfft0:dff0:01:01}), | ||

836 | so we can replace `-' and '+' both with `$\oplus$' to give the | ||

837 | simpler expression | ||

838 | $a(ei \oplus hf) \oplus b(di \oplus gf) \oplus c(dh \oplus ge)$. The | ||

839 | determinants of $A$ and $B$ are thus | ||

840 | |||

841 | \begin{eqnarray} | ||

842 | \nonumber | ||

843 | |A| & = & 1 (1 \cdot 1 \oplus 0 \cdot 1) \oplus | ||

844 | 1 (0 \cdot 1 \oplus 1 \cdot 1) \oplus | ||

845 | 0 (0 \cdot 0 \oplus 1 \cdot 1) \\ | ||

846 | \label{eq:cedc0:sfft0:rmc0:02} | ||

847 | & = & 1 (1 \oplus 0) \oplus 1 (0 \oplus 1) \oplus 0 (0 \oplus 1) \\ | ||

848 | \nonumber | ||

849 | & = & 1 \oplus 1 \oplus 0 = 0 | ||

850 | \end{eqnarray} | ||

851 | |||

852 | \noindent{}and | ||

853 | |||

854 | \begin{eqnarray} | ||

855 | \nonumber | ||

856 | |B| & = & 1 (1 \cdot 1 \oplus 0 \cdot 1) \oplus | ||

857 | 1 (0 \cdot 1 \oplus 0 \cdot 1) \oplus | ||

858 | 0 (0 \cdot 1 \oplus 0 \cdot 1) \\ | ||

859 | \label{eq:cedc0:sfft0:rmc0:03} | ||

860 | & = & 1 (1 \oplus 0) \oplus 1 (0 \oplus 0) \oplus 0 (0 \oplus 0) \\ | ||

861 | \nonumber | ||

862 | & = & 1 \oplus 0 \oplus 0 = 1 . | ||

863 | \end{eqnarray} | ||

864 | |||

865 | From the determinants, it follows that $B$ is of full rank ($rank(B)=3$) but $A$ is not. | ||

866 | In fact, | ||

867 | it can be seen on inspection of $A$ that the third row is the sum of the first | ||

868 | two rows ($rank(A) = 2$). | ||

869 | |||

870 | To enumerate the space spanned by the rows of $A$ and $B$, one can form the sum | ||

871 | $\alpha_0 r_0 \oplus \alpha_1 r_1 \oplus \alpha_2 r_2$ and vary the parameters | ||

872 | $\alpha_0, \alpha_1, \alpha_2 \in \mathbb{B}$. | ||

873 | Table \ref{tbl:cedc0:sfft0:rmc0:01} supplies this range for | ||

874 | $A$ and Table \ref{tbl:cedc0:sfft0:rmc0:02} supplies this range | ||

875 | for $B$. | ||

876 | |||

877 | \begin{table} | ||

878 | \caption{Range Of $\alpha_0 r_0 \oplus \alpha_1 r_1 \oplus \alpha_2 r_2$ For $A$ Of Example \ref{ex:cedc0:sfft0:rmc0:01}} | ||

879 | \label{tbl:cedc0:sfft0:rmc0:01} | ||

880 | \begin{center} | ||

881 | \begin{tabular}{|c|c|c|l|} | ||

882 | \hline | ||

883 | $\alpha_0$ & $\alpha_1$ & $\alpha_2$ & $\alpha_0 [1 \; 1 \; 0] \oplus \alpha_1 [0 \; 1 \; 1] \oplus \alpha_2 [1 \; 0 \; 1]$ \\ | ||

884 | \hline | ||

885 | \hline | ||

886 | 0 & 0 & 0 & $[0\;0\;0]$ \\ | ||

887 | \hline | ||

888 | 0 & 0 & 1 & $[1\;0\;1]$ \\ | ||

889 | \hline | ||

890 | 0 & 1 & 0 & $[0\;1\;1]$ \\ | ||

891 | \hline | ||

892 | 0 & 1 & 1 & $[0\;1\;1] \oplus [1\;0\;1]$ \\ | ||

893 | & & & $[0 \oplus 1 \;\; 1 \oplus 0\;\; 1 \oplus 1]$ \\ | ||

894 | & & & $[1\;1\;0]$ \\ | ||

895 | \hline | ||

896 | 1 & 0 & 0 & $[1\;1\;0]$ \\ | ||

897 | \hline | ||

898 | 1 & 0 & 1 & $[1\;1\;0] \oplus [1\;0\;1]$ \\ | ||

899 | & & & $[1 \oplus 1 \;\; 1 \oplus 0\;\; 0 \oplus 1]$ \\ | ||

900 | & & & $[0\;1\;1]$ \\ | ||

901 | \hline | ||

902 | 1 & 1 & 0 & $[1\;1\;0] \oplus [0\;1\;1]$ \\ | ||

903 | & & & $[1 \oplus 0 \;\; 1 \oplus 1\;\; 0 \oplus 1]$ \\ | ||

904 | & & & $[1\;0\;1]$ \\ | ||

905 | \hline | ||

906 | 1 & 1 & 1 & $[1\;1\;0] \oplus [0\;1\;1] \oplus [1\;0\;1]$ \\ | ||

907 | & & & $[1 \oplus 0 \oplus 1 \;\; 1 \oplus 1 \oplus 0\;\; 0 \oplus 1 \oplus 1]$ \\ | ||

908 | & & & $[0\;0\;0]$ \\ | ||

909 | \hline | ||

910 | \end{tabular} | ||

911 | \end{center} | ||

912 | \end{table} | ||

913 | |||

914 | \begin{table} | ||

915 | \caption{Range Of $\alpha_0 r_0 \oplus \alpha_1 r_1 \oplus \alpha_2 r_2$ For $B$ Of Example \ref{ex:cedc0:sfft0:rmc0:01}} | ||

916 | \label{tbl:cedc0:sfft0:rmc0:02} | ||

917 | \begin{center} | ||

918 | \begin{tabular}{|c|c|c|l|} | ||

919 | \hline | ||

920 | $\alpha_0$ & $\alpha_1$ & $\alpha_2$ & $\alpha_0 [1 \; 1 \; 0] \oplus \alpha_1 [0 \; 1 \; 1] \oplus \alpha_2 [0 \; 0 \; 1]$ \\ | ||

921 | \hline | ||

922 | \hline | ||

923 | 0 & 0 & 0 & $[0\;0\;0]$ \\ | ||

924 | \hline | ||

925 | 0 & 0 & 1 & $[0\;0\;1]$ \\ | ||

926 | \hline | ||

927 | 0 & 1 & 0 & $[0\;1\;1]$ \\ | ||

928 | \hline | ||

929 | 0 & 1 & 1 & $[0\;1\;1] \oplus [0\;0\;1]$ \\ | ||

930 | & & & $[0 \oplus 0 \;\; 1 \oplus 0\;\; 1 \oplus 1]$ \\ | ||

931 | & & & $[0\;1\;0]$ \\ | ||

932 | \hline | ||

933 | 1 & 0 & 0 & $[1\;1\;0]$ \\ | ||

934 | \hline | ||

935 | 1 & 0 & 1 & $[1\;1\;0] \oplus [0\;0\;1]$ \\ | ||

936 | & & & $[1 \oplus 0 \;\; 1 \oplus 0\;\; 0 \oplus 1]$ \\ | ||

937 | & & & $[1\;1\;1]$ \\ | ||

938 | \hline | ||

939 | 1 & 1 & 0 & $[1\;1\;0] \oplus [0\;1\;1]$ \\ | ||

940 | & & & $[1 \oplus 0 \;\; 1 \oplus 1\;\; 0 \oplus 1]$ \\ | ||

941 | & & & $[1\;0\;1]$ \\ | ||

942 | \hline | ||

943 | 1 & 1 & 1 & $[1\;1\;0] \oplus [0\;1\;1] \oplus [0\;0\;1]$ \\ | ||

944 | & & & $[1 \oplus 0 \oplus 0 \;\; 1 \oplus 1 \oplus 0\;\; 0 \oplus 1 \oplus 1]$ \\ | ||

945 | & & & $[1\;0\;0]$ \\ | ||

946 | \hline | ||

947 | \end{tabular} | ||

948 | \end{center} | ||

949 | \end{table} | ||

950 | |||

951 | Note from the tables that the rows of $A$ span 4 vectors | ||

952 | (000, 011, 101, and 110), which is consistent | ||

953 | by Lemma \ref{lem:cedc0:sfft0:rmc0:01} with a matrix of rank 2. | ||

954 | Note also that the rows of $B$ span the full space of | ||

955 | $2^3$ vectors (000, 001, 010, 011, 100, 101, 110, and 111), which | ||

956 | is consistent with a full-rank matrix. | ||

957 | \end{vworkexampleparsection} | ||

958 | \vworkexamplefooter{} | ||

959 | |||

960 | |||

961 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

962 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

963 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

964 | \section[Combinatoric Observations] | ||

965 | {Combinatoric Observations About \protect\mbox{\protect\boldmath$(n,k)$} Block Codes} | ||

966 | %Section tag: cob0 | ||

967 | \label{cedc0:scob0} | ||

968 | |||

969 | A surprising number of observations about $(n,k)$ block codes can be made by | ||

970 | simply considering combinatoric aspects of the codes. In Section | ||

971 | \ref{cedc0:scon0:sccb0} and Figure \ref{fig:cedc0:scon0:sccb0:01} | ||

972 | (p. \pageref{fig:cedc0:scon0:sccb0:01}), no assumptions about the function which | ||

973 | maps from the $k$ data bits to the $n-k$ checksum bits (other than determinism) | ||

974 | were made. Even with only the assumption of determinism, a large number of properties | ||

975 | can be derived or deduced, and we do this here. In the following | ||

976 | subsections, it may be necessary to make slightly stronger assumptions in order | ||

977 | to derive properties. | ||

978 | |||

979 | |||

980 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

981 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

982 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

983 | \subsection[Packing Spheres Of Radius \protect\mbox{\protect$\rho$}] | ||

984 | {Surface Area And Volume Of Packing Spheres Of Radius \protect\mbox{\protect\boldmath$\rho$}} | ||

985 | %Subsection tag: psr0 | ||

986 | \label{cedc0:scob0:psr0} | ||

987 | |||

988 | As discussed in Section \ref{cedc0:scon0:sccb0}, we are interested in constructing | ||

989 | messages consisting of $n$ symbols from the binary alphabet | ||

990 | |||

991 | \begin{equation} | ||

992 | \label{eq:cedc0:scob0:psr0:01} | ||

993 | \mathbb{B} = \{ 0, 1 \} , | ||

994 | \end{equation} | ||

995 | |||

996 | \noindent{}with $k$ symbols being arbitrarily chosen (data), and the remaining | ||

997 | $n-k$ symbols being check bits. | ||

998 | |||

999 | As mentioned in Section \ref{cedc0:scon0:secv0}, the minimum Hamming distance | ||

1000 | $\hat{d}$ | ||

1001 | of a | ||

1002 | code is related to its error detection capability (Eq. \ref{eq:cedc0:scon0:secv0:01}) | ||

1003 | and to its error correction capability (Eq. \ref{eq:cedc0:scon0:secv0:04}). | ||

1004 | It is most natural to think of the minimum Hamming distance $\hat{d}$ of a code | ||

1005 | in terms of disjoint packing spheres or radius $\rho$, where $\hat{d} = 2 \rho + 1$, | ||

1006 | rather than considering Hamming distance directly. In this section, we | ||

1007 | derive the surface area\footnote{To use \emph{surface area} in this way is perhaps | ||

1008 | a mild abuse of nomenclature.} and volume of packing spheres. | ||

1009 | |||

1010 | We define the surface area of a packing sphere of radius $\rho$ to be the | ||

1011 | number of messages which are exactly at Hamming distance $\rho$ from a message | ||

1012 | being considered. To say that a message $c_2$ is exactly at distance | ||

1013 | $\rho$ from $c_1$ is equivalent to saying that the error vector has weight $\rho$. | ||

1014 | |||

1015 | Thus, for an $(n,k)$ block code, the number of messages that are precisely | ||

1016 | at a distance $\rho$ from another message is given by | ||

1017 | |||

1018 | \begin{equation} | ||

1019 | \label{eq:cedc0:scob0:psr0:02} | ||

1020 | S(n, \rho ) = \left({\begin{array}{cc}n\\\rho\end{array}}\right) . | ||

1021 | \end{equation} | ||

1022 | |||

1023 | \noindent{}This formula comes directly from considering the | ||

1024 | number of $n$-bit error vectors of weight $\rho$ that can be constructed. | ||

1025 | |||

1026 | We define the volume of a packing sphere of radius $\rho$ to be the | ||

1027 | number of messages which are at a distance $\rho$ or less from a | ||

1028 | message being considered. This volume can be obtained by | ||

1029 | simply summing the number of messages at distances | ||

1030 | $0 \leq d \leq \rho$ from the message being considered: | ||

1031 | |||

1032 | \begin{eqnarray} | ||

1033 | \label{eq:cedc0:scob0:psr0:03} | ||

1034 | V(n, \rho ) & = & \sum_{d=0}^{\rho} \left({\begin{array}{cc}n\\d\end{array}}\right) \\ | ||

1035 | \nonumber | ||

1036 | & = & 1 | ||

1037 | + \left({\begin{array}{cc}n\\1\end{array}}\right) | ||

1038 | + \left({\begin{array}{cc}n\\2\end{array}}\right) | ||

1039 | + \ldots{} | ||

1040 | + \left({\begin{array}{cc}n\\\rho\end{array}}\right) | ||

1041 | \end{eqnarray} | ||

1042 | |||

1043 | \noindent{}Note in (\ref{eq:cedc0:scob0:psr0:03}) | ||

1044 | that $d=0$ is included because the messsage being considered | ||

1045 | (at distance 0) is also within the sphere. Note also that there is no | ||

1046 | way to simplify the summation in (\ref{eq:cedc0:scob0:psr0:03}). | ||

1047 | |||

1048 | |||

1049 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1050 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1051 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1052 | \subsection[Relationship Between Number Of Check Bits | ||

1053 | \protect\mbox{\protect$n-k$} | ||

1054 | And Minimum Hamming | ||

1055 | Distance \protect\mbox{\protect$\hat{d}$}] | ||

1056 | {Relationship Between Number Of Check Bits | ||

1057 | \protect\mbox{\protect\boldmath$n-k$} | ||

1058 | And Minimum Hamming | ||

1059 | Distance \protect\mbox{\protect\boldmath$\hat{d}$}} | ||

1060 | %Subsection tag: rbc0 | ||

1061 | \label{cedc0:scob0:rbc0} | ||

1062 | |||

1063 | Given that we wish to reliably transmit or store $k$ data bits, | ||

1064 | we are interested in discovering how much protection (in terms of the | ||

1065 | minimum Hamming distance $\hat{d}$) we can purchase with $n-k$ check bits. | ||

1066 | In this section, | ||

1067 | we develop | ||

1068 | fundamental limiting | ||

1069 | relationships between $n$, $k$, and $\hat{d}$ for $(n,k)$ block codes. | ||

1070 | |||

1071 | |||

1072 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1073 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1074 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1075 | \subsubsection{Absolute Upper Limit} | ||

1076 | %Subsubsection tag: aul0 | ||

1077 | \label{cedc0:scob0:rbc0:saul0} | ||

1078 | |||

1079 | The \index{Singleton bound}Singleton bound (Lemma \ref{lem:cedc0:slco0:spcd0:03}) | ||

1080 | can also be proved combinationally using the | ||

1081 | pigeonhole principle. | ||

1082 | |||

1083 | It is obvious combinationally that \emph{no code can detect more than | ||

1084 | $n-k$ corruptions} (this is a restatement of the Singleton bound given in | ||

1085 | Lemma \ref{lem:cedc0:slco0:spcd0:03}). To understand why this must be true, | ||

1086 | choose $m = n-k+1$ bits among the $k$ data bits to vary. Note that there | ||

1087 | are $2^m$ patterns for the $m$ data bits, but only $2^{n-k}$ patterns for the | ||

1088 | $n-k$ check bits. Thus, by the pigeonhole principle, at least one pair of patterns among the | ||

1089 | data bits maps to the same pattern among the check bits. Thus, we can generate two | ||

1090 | codewords having the same check bits by varying $m$ of the $k$ data bits, and thus we can | ||

1091 | change one codeword to another with $n-k+1$ corruptions. | ||

1092 | |||

1093 | |||

1094 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1095 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1096 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1097 | \subsubsection{Hamming (Sphere-Packing) Bound} | ||

1098 | %Subsubsection tag: hsp0 | ||

1099 | \label{cedc0:scob0:rbc0:shsp0} | ||

1100 | |||

1101 | The most obvious bound comes about by considering that for a code with a | ||

1102 | minimum Hamming distance $\hat{d}$ (assumed odd), the $2^k$ packing spheres each with | ||

1103 | volume $V(n, \rho = (\hat{d}-1)/2 )$ must ``fit'' in the space | ||

1104 | of $2^n$ messages that can be formed. This immediately leads to the | ||

1105 | constraint | ||

1106 | |||

1107 | \begin{equation} | ||

1108 | \label{eq:cedc0:scob0:rbc0:shsp0:01} | ||

1109 | 2^k V(n, \rho) \leq 2^n . | ||

1110 | \end{equation} | ||

1111 | |||

1112 | \noindent{}(\ref{eq:cedc0:scob0:rbc0:shsp0:01}) states that the number of codewords | ||

1113 | ($2^k$ of them, one for each possible combination of the $k$ data bits) multiplied | ||

1114 | by the number of messages required to populate a packing sphere around each codeword | ||

1115 | adequate to guarantee | ||

1116 | the minimum Hammming distance must be less than the number of message patterns | ||

1117 | available ($2^n$ of them, one for each possible combination of the $n$ message bits). | ||

1118 | Note that (\ref{eq:cedc0:scob0:rbc0:shsp0:01}) is a necessary condition for the existence | ||

1119 | of a code with | ||

1120 | a minimum Hamming distance of $\hat{d} = 2 \rho + 1$, but not a sufficient condition. | ||

1121 | |||

1122 | |||

1123 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1124 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1125 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1126 | \subsection{Linear Codes} | ||

1127 | %Subection tag: lco0 | ||

1128 | \label{cedc0:scon0:slco0} | ||

1129 | |||

1130 | |||

1131 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1132 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1133 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1134 | \subsection{Burst Errors} | ||

1135 | %Subection tag: bhe0 | ||

1136 | \label{cedc0:scon0:sbhe0} | ||

1137 | |||

1138 | Need to define burst error capability $d_B$ as the size of the frame | ||

1139 | in which unlimited errors may occur. | ||

1140 | |||

1141 | |||

1142 | |||

1143 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1144 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1145 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1146 | \subsection{Metrics Of Goodness} | ||

1147 | %Subection tag: mgo0 | ||

1148 | \label{cedc0:scon0:smgo0} | ||

1149 | |||

1150 | Given multiple possible strategies for implementing an error-detecting | ||

1151 | or error-correcting code, how does one decide that one strategy is | ||

1152 | better than another? What are the characteristics of merit | ||

1153 | (or metrics of goodness) which should be used to rate strategies? This | ||

1154 | question is especially relevant to microcontroller work, where strategies may | ||

1155 | be chosen for efficiency and so may have some benefits but may not | ||

1156 | have all mathematical properties normally associated with error detecting | ||

1157 | and error correcting codes. | ||

1158 | |||

1159 | We propose the following metrics of goodness for error detection and correction | ||

1160 | strategies. | ||

1161 | |||

1162 | \begin{enumerate} | ||

1163 | \item \label{enum:cedc0:scon0:smgo0:01:01} | ||

1164 | \textbf{Execution Time:} | ||

1165 | Particularly for ROM checksum strategies that execute at product startup | ||

1166 | or protect large blocks of data, execution time is critical. We | ||

1167 | accept the TMS370C8 with a 12Mhz crystal as | ||

1168 | a protypical inexpensive microcontroller, and | ||

1169 | we express execution time as a linear model with offset. If | ||

1170 | $m$ is the number of bytes to be protected (including the | ||

1171 | checksum), we parameterize the performance by $t_s$ and $t_d$ so that | ||

1172 | the time $t_{EX}$ to calculate the checksum is given by | ||

1173 | |||

1174 | \begin{equation} | ||

1175 | \label{eq:cedc0:scon0:smgo0:01} | ||

1176 | t_{EX} = t_s + m t_d . | ||

1177 | \end{equation} | ||

1178 | |||

1179 | The parameter $t_s$ is included to properly characterize algorithms that have | ||

1180 | a large setup or cleanup time. Note also that any differences between | ||

1181 | algorithms in the size | ||

1182 | of the checksum are accounted for by defining $m$ to include the checksum and | ||

1183 | suitably adjusting $t_s$ (however, note that any such adjustments will be | ||

1184 | \emph{very} small, as the checksum is typically very small in relation to the | ||

1185 | data being protected). | ||

1186 | |||

1187 | \item \label{enum:cedc0:scon0:smgo0:01:02} | ||

1188 | \textbf{Minimum Hamming Distance \mbox{\boldmath$\hat{d}$} Of The Code:} | ||

1189 | This is a very useful metric, and a larger $\hat{d}$ is better. However, | ||

1190 | this metric can be misleading, and so the metric immediately below is also | ||

1191 | applied. | ||

1192 | |||

1193 | \item \label{enum:cedc0:scon0:smgo0:01:03} | ||

1194 | \textbf{Probability Of Undetected Corruption As A Function Of \mbox{\boldmath$p$}:} | ||

1195 | In microcontroller work, the minimum Hamming distance $\hat{d}$ of a | ||

1196 | code may not give a complete metric for evaluation. For example, it | ||

1197 | may be possible in practice to devise an efficient code such that nearly all | ||

1198 | codewords are separated by a large Hamming distance but a small fraction | ||

1199 | of codewords are separated by a small Hamming distance. In such a case, | ||

1200 | the minimum Hamming distance $\hat{d}$ may not reflect the actual goodness | ||

1201 | of the code. We are very interested in the actual probabilities of undetected | ||

1202 | corruption as a function of $p$ when random bits are chosen to corrupt. | ||

1203 | |||

1204 | \item \label{enum:cedc0:scon0:smgo0:01:04} | ||

1205 | \textbf{Applicability Of The Code As An Error-Correcting Code:} | ||

1206 | A code with a minimum Hamming distance $\hat{d}$ of at least 3 can be harnessed as | ||

1207 | an error-correcting code. However, the cost of the decoding step needs to be | ||

1208 | considered. Two questions are of interest: | ||

1209 | |||

1210 | \begin{enumerate} | ||

1211 | \item \textbf{Is a practical algorithm known for decoding (i.e. for mapping from the | ||

1212 | message received to the nearest codeword)?} It may be possible to devise codes | ||

1213 | with $\hat{d} \geq 3$ that are not practical to decode. | ||

1214 | \item \textbf{What is the cost of this algorithm?} The cost would be parameterized | ||

1215 | as in (\ref{eq:cedc0:scon0:smgo0:01}). | ||

1216 | \end{enumerate} | ||

1217 | \end{enumerate} | ||

1218 | |||

1219 | |||

1220 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1221 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1222 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1223 | \section{Linear Codes} | ||

1224 | %Section tag: lco0 | ||

1225 | \label{cedc0:slco0} | ||

1226 | |||

1227 | |||

1228 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1229 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1230 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1231 | \subsection{Definition} | ||

1232 | \label{cedc0:slco0:sdef0} | ||

1233 | |||

1234 | A linear code is simply a subspace of $\mathbb{B}^n$. In this definition, | ||

1235 | by \emph{subspace} we mean subspace in the conventional linear algebra | ||

1236 | sense where the subspace is spanned by linear combinations of a set of vectors, | ||

1237 | and we operate within the finite field $GF(2)$ for each vector or matrix element. | ||

1238 | |||

1239 | As an example of a linear code, consider the $(5,3)$ block code consisting | ||

1240 | of vectors of the form $[a\;b\;c\;d\;e]$ where $d = a \oplus b$ and | ||

1241 | $e = b \oplus c$. Such a code can be characterized by a generator | ||

1242 | matrix | ||

1243 | |||

1244 | \begin{equation} | ||

1245 | \label{eq:cedc0:slco0:sdef0:01} | ||

1246 | G = \left[ | ||

1247 | \begin{array}{ccccc} | ||

1248 | 1&0&0&1&0 \\ | ||

1249 | 0&1&0&1&1 \\ | ||

1250 | 0&0&1&0&1 | ||

1251 | \end{array} | ||

1252 | \right] | ||

1253 | \end{equation} | ||

1254 | |||

1255 | \noindent{}where any codeword in the code is a linear combination of the rows | ||

1256 | of $G$. | ||

1257 | |||

1258 | We can calculate all of the codewords in the code defined by $G$ by | ||

1259 | forming all of the linear combinations of the rows of $G$. | ||

1260 | A linear combination of the rows of $G$ is of the form | ||

1261 | |||

1262 | \begin{equation} | ||

1263 | \label{eq:cedc0:slco0:sdef0:02} | ||

1264 | \alpha_0 [1\;0\;0\;1\;0] | ||

1265 | \oplus | ||

1266 | \alpha_1 [0\;1\;0\;1\;1] | ||

1267 | \oplus | ||

1268 | \alpha_2 [0\;0\;1\;0\;1], | ||

1269 | \end{equation} | ||

1270 | |||

1271 | \noindent{}where $\alpha_0, \alpha_1, \alpha_2 \in \mathbb{B}$. | ||

1272 | It can be verified that the codewords formed by varying | ||

1273 | $\alpha_0, \alpha_1, \alpha_2$ in (\ref{eq:cedc0:slco0:sdef0:02}) | ||

1274 | are 00000, 00101, 01011, 01110, 10010, 10111, 11001, and 11100. | ||

1275 | |||

1276 | There are many properties of linear codes that follow immediately | ||

1277 | from the definition of a linear code as a subspace. However, we | ||

1278 | delay introducing these properties until Section \ref{cedc0:slco0:splc0}, | ||

1279 | until after the parity check matrix (Section \ref{cedc0:slco0:spcm0}) and the | ||

1280 | generator matrix (Section \ref{cedc0:slco0:sgma0}) have been introduced. | ||

1281 | |||

1282 | |||

1283 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1284 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1285 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1286 | \subsection{The Parity Check Matrix} | ||

1287 | \label{cedc0:slco0:spcm0} | ||

1288 | |||

1289 | Any linear code can be characterized by a | ||

1290 | \index{parity check matrix}\emph{parity check matrix} $H$ such that | ||

1291 | for any codeword $m = [m_0, m_1, \ldots{}, m_{n-1}]$ in the | ||

1292 | code, | ||

1293 | |||

1294 | \begin{equation} | ||

1295 | \label{eq:cedc0:slco0:spcm0:01} | ||

1296 | H m^T = \mathbf{0} . | ||

1297 | \end{equation} | ||

1298 | |||

1299 | \noindent{}More explicitly, we may write (\ref{eq:cedc0:slco0:spcm0:01}) | ||

1300 | as | ||

1301 | |||

1302 | \begin{equation} | ||

1303 | \label{eq:cedc0:slco0:spcm0:02} | ||

1304 | \left[\begin{array}{llcl} | ||

1305 | h_{0,0} & h_{0,1} & \cdots{} & h_{0,n-1} \\ | ||

1306 | h_{1,0} & h_{1,1} & \cdots{} & h_{1,n-1} \\ | ||

1307 | \;\;\vdots & \;\;\vdots & \ddots{} & \;\;\vdots \\ | ||

1308 | h_{n-k-1,0} & h_{n-k-1,1} & \cdots{} & h_{n-k-1,n-1} \\ | ||

1309 | \end{array}\right] | ||

1310 | \left[\begin{array}{l}m_0\\m_1\\\;\;\vdots{}\\m_{n-1}\end{array}\right] | ||

1311 | = \left[\begin{array}{c}0\\0\\\vdots{}\\0\end{array}\right] | ||

1312 | \end{equation} | ||

1313 | |||

1314 | \noindent{}where of course | ||

1315 | |||

1316 | \begin{equation} | ||

1317 | \label{eq:cedc0:slco0:spcm0:03} | ||

1318 | H = \left[\begin{array}{llcl} | ||

1319 | h_{0,0} & h_{0,1} & \cdots{} & h_{0,n-1} \\ | ||

1320 | h_{1,0} & h_{1,1} & \cdots{} & h_{1,n-1} \\ | ||

1321 | \;\;\vdots & \;\;\vdots & \ddots{} & \;\;\vdots \\ | ||

1322 | h_{n-k-1,0} & h_{n-k-1,1} & \cdots{} & h_{n-k-1,n-1} \\ | ||

1323 | \end{array}\right] | ||

1324 | \end{equation} | ||

1325 | |||

1326 | \noindent{}and | ||

1327 | |||

1328 | \begin{equation} | ||

1329 | \label{eq:cedc0:slco0:spcm0:04} | ||

1330 | m^T = | ||

1331 | \left[\begin{array}{l}m_0\\m_1\\\;\;\vdots{}\\m_{n-1}\end{array}\right] . | ||

1332 | \end{equation} | ||

1333 | |||

1334 | Note that $H$ has the same number of columns as message bits and | ||

1335 | the same number of rows as check bits. | ||

1336 | |||

1337 | Each row of $H$ specifies a required relationship between two or more | ||

1338 | message bits. In the case of (\ref{eq:cedc0:slco0:spcm0:02}), these | ||

1339 | $n-k$ relationships are | ||

1340 | |||

1341 | \begin{eqnarray} | ||

1342 | \nonumber h_{0,0} m_{0} + h_{0,1} m_{1} + \cdots{} h_{0,n-1} m_{n-1} & = & 0 \\ | ||

1343 | \label{eq:cedc0:slco0:spcm0:05} | ||

1344 | h_{1,0} m_{1} + h_{1,1} m_{1} + \cdots{} h_{1,n-1} m_{n-1} & = & 0 \\ | ||

1345 | \nonumber & \vdots & \\ | ||

1346 | \nonumber h_{n-k-1,0} m_{0} + h_{n-k-1,1} m_{1} + \cdots{} h_{n-k-1,n-1} m_{n-1} & = & 0 | ||

1347 | \end{eqnarray} | ||

1348 | |||

1349 | In the general case $H$ is arbitrary except that each row must | ||

1350 | have at least two non-zero elements. However, because we are | ||

1351 | interested only in codes where the check bits are concatenated | ||

1352 | to the data bits (see Section \ref{cedc0:scon0:sccb0} and Figure | ||

1353 | \ref{fig:cedc0:scon0:sccb0:01}), it is immediately | ||

1354 | apparent that each row of $H$ must have at least one non-zero entry | ||

1355 | in columns $n-k$ through $n-1$. If this condition were not met, $H$ would | ||

1356 | specify a required | ||

1357 | relationship between the $k$ data bits, which would mean that the $k$ data bits | ||

1358 | could not be chosen freely. | ||

1359 | |||

1360 | For the case where $n-k$ check bits are appended to $k$ data bits, we | ||

1361 | seek to describe the code by a parity check matrix $H$ where the | ||

1362 | rightmost $n-k$ columns are the identity matrix. If $H$ is arranged in this | ||

1363 | way, each row of $H$ defines one of the $n-k$ check bits in terms of the $k$ data bits. | ||

1364 | In other words, we generally seek to write $H$ as a concatenated matrix | ||

1365 | |||

1366 | \begin{equation} | ||

1367 | \label{eq:cedc0:slco0:spcm0:06} | ||

1368 | H_{n-k \times n} = [H'_{n-k \times k} | I_{n-k \times n-k} ], | ||

1369 | \end{equation} | ||

1370 | |||

1371 | \noindent{}where the subscripts provide the dimensions of the matrices. | ||

1372 | If $H$ is not arranged in this way, it can be arranged in this way by elementary | ||

1373 | row operations. | ||

1374 | |||

1375 | We illustrate the application of the a parity generation matrix $H$ with the following | ||

1376 | example. | ||

1377 | |||

1378 | \begin{vworkexamplestatement} | ||

1379 | \label{ex:cedc0:slco0:spcm0:01} | ||

1380 | For a $(7,4)$ code where each message is a row vector | ||

1381 | |||

1382 | \begin{equation} | ||

1383 | \label{eq:ex:cedc0:slco0:spcm0:01:01} | ||

1384 | [ d_0 \; d_1 \; d_2 \; d_3 \; c_0 \; c_1 \; c_2 ] | ||

1385 | \end{equation} | ||

1386 | |||

1387 | \noindent{}and where the parity check matrix is | ||

1388 | |||

1389 | \begin{equation} | ||

1390 | \label{eq:ex:cedc0:slco0:spcm0:01:02} | ||

1391 | H = \left[\begin{array}{ccccccc} | ||

1392 | 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ | ||

1393 | 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ | ||

1394 | 0 & 1 & 1 & 1 & 0 & 0 & 1 | ||

1395 | \end{array}\right], | ||

1396 | \end{equation} | ||

1397 | |||

1398 | \noindent{}find expressions for the check bits $c_0$, $c_1$, and $c_2$; and | ||

1399 | enumerate the complete code. | ||

1400 | \end{vworkexamplestatement} | ||

1401 | \begin{vworkexampleparsection}{Solution} | ||

1402 | Note that $H$ is already conditioned so that the rightmost $n-k$ columns | ||

1403 | are the identity matrix. By the definition provided by | ||

1404 | (\ref{eq:cedc0:slco0:spcm0:06}), | ||

1405 | |||

1406 | \begin{equation} | ||

1407 | \label{eq:ex:cedc0:slco0:spcm0:01:02b} | ||

1408 | H'_{(n-k \times k) = (3 \times 4)} = \left[\begin{array}{cccc} | ||

1409 | 1 & 1 & 0 & 1 \\ | ||

1410 | 1 & 0 & 1 & 1 \\ | ||

1411 | 0 & 1 & 1 & 1 | ||

1412 | \end{array}\right] | ||

1413 | \end{equation} | ||

1414 | |||

1415 | \noindent{}and | ||

1416 | |||

1417 | \begin{equation} | ||

1418 | \label{eq:ex:cedc0:slco0:spcm0:01:02c} | ||

1419 | I_{(n-k \times n-k) = (3 \times 3)}= \left[\begin{array}{ccc} | ||

1420 | 1 & 0 & 0 \\ | ||

1421 | 0 & 1 & 0 \\ | ||

1422 | 0 & 0 & 1 | ||

1423 | \end{array}\right]. | ||

1424 | \end{equation} | ||

1425 | |||

1426 | Applying (\ref{eq:cedc0:slco0:spcm0:01}) yields | ||

1427 | |||

1428 | \begin{equation} | ||

1429 | \label{eq:ex:cedc0:slco0:spcm0:01:03} | ||

1430 | \left[\begin{array}{ccccccc} | ||

1431 | 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ | ||

1432 | 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ | ||

1433 | 0 & 1 & 1 & 1 & 0 & 0 & 1 | ||

1434 | \end{array}\right] | ||

1435 | \left[\begin{array}{c}d_0\\d_1\\d_2\\d_3\\c_0\\c_1\\c_2\end{array}\right] = | ||

1436 | \left[\begin{array}{c}0\\0\\0\\0\\0\\0\\0\end{array}\right] , | ||

1437 | \end{equation} | ||

1438 | |||

1439 | \noindent{}or equivalently the system of equations | ||

1440 | |||

1441 | \begin{eqnarray} | ||

1442 | \nonumber | ||

1443 | d_0 \oplus d_1 \oplus d_3 \oplus c_0 & = & 0 \\ | ||

1444 | \label{eq:ex:cedc0:slco0:spcm0:01:05} | ||

1445 | d_0 \oplus d_2 \oplus d_3 \oplus c_1 & = & 0 \\ | ||

1446 | \nonumber | ||

1447 | d_1 \oplus d_2 \oplus d_3 \oplus c_2 & = & 0 . | ||

1448 | \end{eqnarray} | ||

1449 | |||

1450 | \noindent{}The system of equations (\ref{eq:ex:cedc0:slco0:spcm0:01:05}) | ||

1451 | can be solved for $c_0$, $c_1$, and $c_2$ by using | ||

1452 | Property \ref{prop:cedc0:scon0:sxor0:01:04} | ||

1453 | from Section \ref{cedc0:scon0:sxor0}, which allows $c_0$, $c_1$ and $c_2$ to | ||

1454 | be moved to the other side of the equations in (\ref{eq:ex:cedc0:slco0:spcm0:01:05}), | ||

1455 | yielding | ||

1456 | |||

1457 | \begin{eqnarray} | ||

1458 | \nonumber | ||

1459 | c_0 & = & d_0 \oplus d_1 \oplus d_3 \\ | ||

1460 | \label{eq:ex:cedc0:slco0:spcm0:01:08} | ||

1461 | c_1 & = & d_0 \oplus d_2 \oplus d_3 \\ | ||

1462 | \nonumber | ||

1463 | c_2 & = & d_1 \oplus d_2 \oplus d_3 . | ||

1464 | \end{eqnarray} | ||

1465 | |||

1466 | The full code can be enumerated by listing all $2^k = 2^4 = 16$ combinations of | ||

1467 | the data bits $d_0\ldots{}d_3$ and then applying (\ref{eq:ex:cedc0:slco0:spcm0:01:08}) | ||

1468 | to obtain $c_0$, $c_1$, and $c_2$. Table \ref{tbl:ex:cedc0:slco0:spcm0:01:01} | ||

1469 | supplies the full code obtained in this way. | ||

1470 | |||

1471 | \begin{table} | ||

1472 | \caption{Fully Enumerated (7,4) Code (Solution To Example \ref{ex:cedc0:slco0:spcm0:01})} | ||

1473 | \label{tbl:ex:cedc0:slco0:spcm0:01:01} | ||

1474 | \begin{center} | ||

1475 | \begin{tabular}{|c|c|c|c|c|c|c|} | ||

1476 | \hline | ||

1477 | $d_0$ & $d_1$ & $d_2$ & $d_3$ & $c_0$ & $c_1$ & $c_2$ \\ | ||

1478 | & & & & $=d_0 \oplus d_1 \oplus d_3$ & $=d_0 \oplus d_2 \oplus d_3$ & $=d_1 \oplus d_2 \oplus d_3$ \\ | ||

1479 | \hline | ||

1480 | \hline | ||

1481 | 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ | ||

1482 | \hline | ||

1483 | 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ | ||

1484 | \hline | ||

1485 | 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ | ||

1486 | \hline | ||

1487 | 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ | ||

1488 | \hline | ||

1489 | 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ | ||

1490 | \hline | ||

1491 | 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ | ||

1492 | \hline | ||

1493 | 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ | ||

1494 | \hline | ||

1495 | 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ | ||

1496 | \hline | ||

1497 | 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ | ||

1498 | \hline | ||

1499 | 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ | ||

1500 | \hline | ||

1501 | 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ | ||

1502 | \hline | ||

1503 | 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ | ||

1504 | \hline | ||

1505 | 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ | ||

1506 | \hline | ||

1507 | 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ | ||

1508 | \hline | ||

1509 | 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ | ||

1510 | \hline | ||

1511 | 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ | ||

1512 | \hline | ||

1513 | \end{tabular} | ||

1514 | \end{center} | ||

1515 | \end{table} | ||

1516 | \end{vworkexampleparsection} | ||

1517 | \vworkexamplefooter{} | ||

1518 | |||

1519 | In the first paragraph of this section, we made the claim that \emph{any} linear | ||

1520 | code can be represented by a parity check matrix. We substantiate that | ||

1521 | claim with the following lemma. | ||

1522 | |||

1523 | \begin{vworklemmastatement} | ||

1524 | \label{lem:cedc0:slco0:spcm0:01} | ||

1525 | Every linear code can be represented by a parity check matrix, and every | ||

1526 | parity check matrix defines a linear code. | ||

1527 | \end{vworklemmastatement} | ||

1528 | \begin{vworklemmaproof} | ||

1529 | We first prove that a code $C$ specified by a parity check matrix $H$ | ||

1530 | is a linear code. Note that $\mathbf{0} \in C$ (which is required for a linear code), | ||

1531 | since $H \mathbf{0}^T = \mathbf{0}$. If $m_1 \in C$ and $m_2 \in C$, then | ||

1532 | by definition $H m_1^T = H m_2^T = \mathbf{0}$. It can be shown by linearity | ||

1533 | that $H (m_3^T = (m_1 + m_2)^T) = \mathbf{0}$, and thus $m_3 \in C$. | ||

1534 | |||

1535 | We then prove the implication in the other direction; that any linear code must be | ||

1536 | describable by a parity matrix $H$. Although this is true in the general | ||

1537 | case, we prove it only for the case of the type of code involving | ||

1538 | $n-k$ check bits appended to $k$ data bits, as described in | ||

1539 | Section \ref{cedc0:scon0:sccb0} and Figure | ||

1540 | \ref{fig:cedc0:scon0:sccb0:01}. This type of code contains a codeword | ||

1541 | for all possible values of the data bits $d_0 \ldots d_{k-1}$. We | ||

1542 | consider only those codewords which have a single data bit set. Figure | ||

1543 | \ref{tbl:lem:cedc0:slco0:spcm0:01:01} enumerates such codewords extracted | ||

1544 | from Example \ref{ex:cedc0:slco0:spcm0:01} and Figure | ||

1545 | \ref{tbl:ex:cedc0:slco0:spcm0:01:01}. | ||

1546 | |||

1547 | \begin{table} | ||

1548 | \caption{Codewords From Example \ref{ex:cedc0:slco0:spcm0:01} With Only A Single Data Bit Set} | ||

1549 | \label{tbl:lem:cedc0:slco0:spcm0:01:01} | ||

1550 | \begin{center} | ||

1551 | \begin{tabular}{|c|c|c|c|c|c|c|} | ||

1552 | \hline | ||

1553 | $d_0$ & $d_1$ & $d_2$ & $d_3$ & $c_0$ & $c_1$ & $c_2$ \\ | ||

1554 | \hline | ||

1555 | \hline | ||

1556 | 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ | ||

1557 | \hline | ||

1558 | 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ | ||

1559 | \hline | ||

1560 | 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ | ||

1561 | \hline | ||

1562 | 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ | ||

1563 | \hline | ||

1564 | \end{tabular} | ||

1565 | \end{center} | ||

1566 | \end{table} | ||

1567 | |||

1568 | Because of the linearity of the code, we are able to construct any | ||

1569 | codeword of the code from a set of codewords such as are | ||

1570 | shown in Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01}. Given | ||

1571 | any four data bits $d_0 \ldots d_3$, we form the codeword | ||

1572 | by adding together the rows corresponding to the 1's in the | ||

1573 | data. For example, to form the codeword corresponding to | ||

1574 | $[d_0 d_1 d_2 d_3]$ $=$ $[1010]$, we would simply XOR together | ||

1575 | the the first and third rows from Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01}: | ||

1576 | $[1000111] \oplus [0010011] = [1010100]$. | ||

1577 | |||

1578 | However, the structure of Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01} | ||

1579 | gives us somewhat more information about the structure of a parity | ||

1580 | generation matrix $H$. In the first row, with only $d_0$ set to 1, | ||

1581 | $c_0$, $c_1$, and $c_2$ are all 1: this indicates that $d_0$ must appear in the | ||

1582 | parity equations for $c_0$, $c_1$, and $c_2$. Similarly, the second row indicates | ||

1583 | that $d_1$ appears in the parity equations for $c_0$ and $c_2$ only. | ||

1584 | One can thus derive (\ref{eq:ex:cedc0:slco0:spcm0:01:08}) directly | ||

1585 | from examining the last three columns of Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01}. | ||

1586 | Using the observations above, a parity check matrix which provides data consistent | ||

1587 | with Table \ref{tbl:lem:cedc0:slco0:spcm0:01:01} can be constructed. Since | ||

1588 | the code being considered and the code formed by the parity check matrix | ||

1589 | constructed as described above are both linear, it follows that the two codes | ||

1590 | are identical. Thus, using the procedure described above, | ||

1591 | a parity check matrix can be constructed for any linear code consisting of | ||

1592 | $n-k$ check bits appended to $k$ data bits. | ||

1593 | \end{vworklemmaproof} | ||

1594 | \vworklemmafooter{} | ||

1595 | |||

1596 | |||

1597 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1598 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1599 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1600 | \subsection{The Generator Matrix} | ||

1601 | \label{cedc0:slco0:sgma0} | ||

1602 | |||

1603 | A second characterization of a linear code is | ||

1604 | by a \index{generator matrix}generator matrix. A generator matrix is | ||

1605 | a set of codewords chosen to be a minimal basis set for the code so that | ||

1606 | all other codewords can be calculated by linearly combining codewords | ||

1607 | in the generator matrix. | ||

1608 | |||

1609 | The generator matrix for the code from Example \ref{ex:cedc0:slco0:spcm0:01} is | ||

1610 | |||

1611 | \begin{equation} | ||

1612 | \label{eq:cedc0:slco0:sgma0:01} | ||

1613 | G = \left[ | ||

1614 | \begin{array}{ccccccc} | ||

1615 | 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ | ||

1616 | 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ | ||

1617 | 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ | ||

1618 | 0 & 0 & 0 & 1 & 1 & 1 & 0 | ||

1619 | \end{array} | ||

1620 | \right] . | ||

1621 | \end{equation} | ||

1622 | |||

1623 | \noindent{}Note that this generator matrix also appears as Table | ||

1624 | \ref{tbl:lem:cedc0:slco0:spcm0:01:01}. | ||

1625 | |||

1626 | As with a parity check matrix $H$, we prefer a certain form for | ||

1627 | a generator matrix $G$. This form is exemplified by | ||

1628 | (\ref{eq:cedc0:slco0:sgma0:01}), where $G$ consists of | ||

1629 | the identity matrix with a second matrix concatenated: | ||

1630 | |||

1631 | \begin{equation} | ||

1632 | \label{eq:cedc0:slco0:sgma0:01b} | ||

1633 | G_{k \times n} = [ I_{k \times k} | G'_{k \times n-k}] . | ||

1634 | \end{equation} | ||

1635 | |||

1636 | For the same linear code, there is a simple relationship between the | ||

1637 | parity check matrix $H$ and the generator matrix $G$, assuming that | ||

1638 | $H$ and $G$ are in the forms suggested by equations | ||

1639 | (\ref{eq:cedc0:slco0:spcm0:06}) and (\ref{eq:cedc0:slco0:sgma0:01b}), | ||

1640 | respectively (the forms containing the identity matrix). This | ||

1641 | simple relationship is | ||

1642 | |||

1643 | \begin{equation} | ||

1644 | \label{eq:cedc0:slco0:sgma0:02} | ||

1645 | G' = (H')^T, | ||

1646 | \end{equation} | ||

1647 | |||

1648 | \noindent{}or equivalently | ||

1649 | |||

1650 | \begin{equation} | ||

1651 | \label{eq:cedc0:slco0:sgma0:03} | ||

1652 | H' = (G')^T . | ||

1653 | \end{equation} | ||

1654 | |||

1655 | It is not difficult to intuitively understand | ||

1656 | (\ref{eq:cedc0:slco0:sgma0:02}) and (\ref{eq:cedc0:slco0:sgma0:03}) | ||

1657 | with the aid of Example \ref{ex:cedc0:slco0:spcm0:01} and the definition | ||

1658 | of $H$ and $G$ in | ||

1659 | (\ref{eq:ex:cedc0:slco0:spcm0:01:02}) and | ||

1660 | (\ref{eq:cedc0:slco0:sgma0:01b}), respectively. To go from $H$ to $G$, | ||

1661 | imagine applying the parity check relationship (Eq. \ref{eq:ex:cedc0:slco0:spcm0:01:03}, | ||

1662 | for example) to the unit vector $[d_0 d_1 d_2 d_3] = [1 0 0 0]$. It is easy to see that | ||

1663 | to satisfy the parity check relationship, $c_0$, $c_1$, and $c_2$ will need to be | ||

1664 | set to the values of the first column in $H$, i.e. | ||

1665 | $\left[\begin{array}{c}c_0\\c_1\\c_2\end{array}\right] = \left[\begin{array}{c}1\\1\\0\end{array}\right]$. | ||

1666 | With $[d_0 d_1 d_2 d_3] = [0 1 0 0]$, $c_0$, $c_1$, and $c_2$ will need to be set | ||

1667 | to the values of the second column in $H$, and so on. To go from $G$ to | ||

1668 | $H$, the argument supplied in the proof of Lemma | ||

1669 | \ref{lem:cedc0:slco0:spcm0:01} applies. | ||

1670 | |||

1671 | Thus, as long as they are conditioned properly, the parity check matrix $H$ and the | ||

1672 | generator matrix $G$ are equivalent, and one can translate between the two forms | ||

1673 | by inspection. | ||

1674 | |||

1675 | |||

1676 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1677 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1678 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1679 | \subsection{Properties Of Linear Codes} | ||

1680 | \label{cedc0:slco0:splc0} | ||

1681 | |||

1682 | In this section we present many important properties of linear codes. | ||

1683 | Although most of these properties follow immediately from the observation | ||

1684 | that a linear code is a subspace of $\mathbb{B}^n$ and could have been | ||

1685 | presented in Section \ref{cedc0:slco0:sdef0}, the presentation of these properties | ||

1686 | is best made in terms of the parity check matrix and the generator matrix, | ||

1687 | and so the presentation of these properties was postponed until after the | ||

1688 | parity check matrix and generator matrix were discussed. | ||

1689 | |||

1690 | \begin{vworklemmastatement} | ||

1691 | \label{lem:cedc0:slco0:splc0:01} | ||

1692 | The sum of two or more codewords in a linear code is also a codeword. (This also includes | ||

1693 | adding a codeword to itself.) | ||

1694 | \end{vworklemmastatement} | ||

1695 | \begin{vworklemmaproof} | ||

1696 | This property follows immediately from the definition of a code as a subspace and | ||

1697 | from Lemma \ref{lem:cedc0:sfft0:rmc0:01}. The generator matrix $G$ of a code | ||

1698 | is a $k \times n$ matrix and will always have rank $k$. If we denote the rows of | ||

1699 | the generator matrix as $r_0, r_1, \ldots, r_{k-1}$, then any codeword will be the | ||

1700 | parameterized sum $\alpha_0 r_0 + \alpha_1 r_1 + \ldots + \alpha_{k-1} r_{k-1}$. | ||

1701 | Any sum of codewords will be a sum of this form, and | ||

1702 | superfluous repeated terms can be removed | ||

1703 | (Property \ref{prop:enum:cedc0:sfft0:dff0:01:02}, p. \pageref{prop:enum:cedc0:sfft0:dff0:01:02}), | ||

1704 | leaving only a simple parameterized sum of the form | ||

1705 | $\alpha_0 r_0 + \alpha_1 r_1 + \ldots + \alpha_{k-1} r_{k-1}$, | ||

1706 | with $\alpha_0, \ldots, \alpha_{k-1} \in \mathbb{B}$. | ||

1707 | \end{vworklemmaproof} | ||

1708 | |||

1709 | \begin{vworklemmastatement} | ||

1710 | \label{lem:cedc0:slco0:splc0:02} | ||

1711 | Any linear code includes $\mathbf{0_{1 \times n}}$ as a codeword. | ||

1712 | \end{vworklemmastatement} | ||

1713 | \begin{vworklemmaproof} | ||

1714 | This property is inherent in the traditional linear algebra definition | ||

1715 | of a subspace. As an alternative, we may simply add any codeword to itself | ||

1716 | to obtain $\mathbf{0_{1 \times n}}$, which will then be a codeword | ||

1717 | by Lemma \ref{lem:cedc0:slco0:splc0:01}. | ||

1718 | \end{vworklemmaproof} | ||

1719 | |||

1720 | \begin{vworklemmastatement} | ||

1721 | \label{lem:cedc0:slco0:splc0:03} | ||

1722 | In a linear code, the weight $w$ of a minimum weight codeword (excluding | ||

1723 | $\mathbf{0_{1 \times n}}$) is the minimum Hamming distance | ||

1724 | $\hat{d}$ of the code. | ||

1725 | \end{vworklemmastatement} | ||

1726 | \begin{vworklemmaproof} | ||

1727 | Assume that there are two codewords $c_1, c_2$ such that | ||

1728 | $d(c_1, c_2) < w$. The exclusive-OR of $c_1$ and $c_2$, | ||

1729 | $c_1 \oplus c_2$, | ||

1730 | must also be a codeword (by Lemma \ref{lem:cedc0:slco0:splc0:01}). | ||

1731 | However, note also that $wt(c_1 \oplus c_2)$ is the number of bit | ||

1732 | positions in which $c_1$ and $c_2$ differ, thus | ||

1733 | $c_1 \oplus c_2$ is a codeword in the code with | ||

1734 | $wt(c_1 \oplus c_2) < w$, which contradicts our initial assumption of | ||

1735 | knowing a minimum-weight codeword in the code. | ||

1736 | \end{vworklemmaproof} | ||

1737 | |||

1738 | |||

1739 | |||

1740 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1741 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1742 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1743 | \subsection{Syndrome Decoding} | ||

1744 | \label{cedc0:slco0:ssdc0} | ||

1745 | |||

1746 | A defining equation for linear code membership is given by | ||

1747 | (\ref{eq:cedc0:slco0:spcm0:01}), $H m^T = \mathbf{0}$. For codes harnessed | ||

1748 | for error-detection only, this equation is adequate, as calculating | ||

1749 | $H m^T$ and comparing against $\mathbf{0}$ (i.e. decoding) is an economical operation. | ||

1750 | However, for codes harnessed for error-correction, we seek a way to ``round'' back to the | ||

1751 | nearest codeword. | ||

1752 | |||

1753 | |||

1754 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1755 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1756 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1757 | \subsection[Relationship Between The Parity Check Matrix And \protect\mbox{\protect$\hat{d}$}] | ||

1758 | {Relationship Between The Parity Check Matrix And \protect\mbox{\protect\boldmath$\hat{d}$}} | ||

1759 | \label{cedc0:slco0:spcd0} | ||

1760 | |||

1761 | One of the most important properties of a code is its minimum Hamming distance | ||

1762 | $\hat{d}$. Here we demonstrate the relationship between the parity check matrix | ||

1763 | $H$, the generator matrix $G$, and the minimum Hamming distance $\hat{d}$ of a | ||

1764 | linear code. | ||

1765 | |||

1766 | Upon inspection of the mechanics of the membership condition for a linear | ||

1767 | code, (\ref{eq:cedc0:slco0:spcm0:01}), it is apparent that | ||

1768 | $Hm^T$ is the sum of all columns from $H$ corresponding to a `1' in | ||

1769 | $m$. Thus code membership is tied to the ways in which columns of | ||

1770 | $H$ can be added to give $\mathbf{0}$. | ||

1771 | |||

1772 | The following lemma is immediately apparent. | ||

1773 | |||

1774 | \begin{vworklemmastatement} | ||

1775 | \label{lem:cedc0:slco0:spcd0:01} | ||

1776 | If no fewer than $d$ columns of $H$ can be summed to give $\mathbf{0}$, | ||

1777 | the code has a minimum Hamming distance of $\hat{d}=d$. | ||

1778 | \end{vworklemmastatement} | ||

1779 | \begin{vworklemmaproof} | ||

1780 | Choose any codeword $m \in C$. By definition, | ||

1781 | $Hm^T = \mathbf{0}$, as this is the membership | ||

1782 | condition (\ref{eq:cedc0:slco0:spcm0:01}) for a linear code. We desire | ||

1783 | to modify $m \in C$ by bit corruptions to form a second codeword $m' \in C$, | ||

1784 | and again by definition | ||

1785 | $H(m')^T = \mathbf{0}$. Each bit corruption of $m$ will either include (if a 0 is corrupted | ||

1786 | to a 1) or exclude (if a 1 is corrupted to 0) a | ||

1787 | column of $H$ from the sum which is the $n-k$ check bits. If $Hm^T = \mathbf{0}$, | ||

1788 | then in order for $H(m')^T = \mathbf{0}$, the sum of the included or excluded columns | ||

1789 | must be $\mathbf{0}$. If no fewer than $d$ columns of $H$ sum to $\mathbf{0}$, then | ||

1790 | no fewer than $d$ bit corruptions can change any $m \in C$ to some $m' \in C$. | ||

1791 | \end{vworklemmaproof} | ||

1792 | \vworklemmafooter{} | ||

1793 | |||

1794 | A second lemma is also obvious by examining the form of the | ||

1795 | parity check matrix given in (\ref{eq:cedc0:slco0:spcm0:06}), although | ||

1796 | the result can be proved without this specific form. | ||

1797 | |||

1798 | \begin{vworklemmastatementpar}{Singleton Bound} | ||

1799 | \label{lem:cedc0:slco0:spcd0:03} | ||

1800 | \index{Singleton bound}No code can have a maximum Hamming distance $\hat{d}$ larger than | ||

1801 | $n-k+1$. | ||

1802 | \end{vworklemmastatementpar} | ||

1803 | \begin{vworklemmaparsection}{Proof \#1 (For Linear Codes)} | ||

1804 | Choose any codeword $m \in C$. By definition, | ||

1805 | $Hm^T = \mathbf{0}$, as this is the membership | ||

1806 | condition (\ref{eq:cedc0:slco0:spcm0:01}) for a linear code. We desire | ||

1807 | to modify $m \in C$ by bit corruptions to form a second codeword $m' \in C$, | ||

1808 | and again by definition | ||

1809 | $H(m')^T = \mathbf{0}$. Each bit corruption of $m$ will either include (if a 0 is corrupted | ||

1810 | to a 1) or exclude (if a 1 is corrupted to 0) a | ||

1811 | column of $H$ from the sum which is the $n-k$ check bits. If $Hm^T = \mathbf{0}$, | ||

1812 | then in order for $H(m')^T = \mathbf{0}$, the sum of the included or excluded columns | ||

1813 | must be $\mathbf{0}$. If no fewer than $d$ columns of $H$ sum to $\mathbf{0}$, then | ||

1814 | no fewer than $d$ bit corruptions can change any $m \in C$ to some $m' \in C$. | ||

1815 | \end{vworklemmaparsection} | ||

1816 | \begin{vworklemmaparsection}{Proof \#2 (For Any Code, Not Necessarily Linear)} | ||

1817 | Choose any codeword $m \in C$. Choose any second codeword $m' \in C$, where | ||

1818 | only one bit among the $k$ data bits is different between $m$ and $m'$. Note that we can | ||

1819 | change $m$ into $m'$ through at most $n-k+1$ bit corruptions: one corruption among the $k$ | ||

1820 | data bits and at most $n-k$ corruptions of all check bits. | ||

1821 | \end{vworklemmaparsection} | ||

1822 | \vworklemmafooter{} | ||

1823 | |||

1824 | |||

1825 | |||

1826 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1827 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1828 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1829 | \subsection{Relationship Between The Parity Check Matrix And Burst Error Detection Capability} | ||

1830 | \label{cedc0:slco0:spcb0} | ||

1831 | |||

1832 | For any code, linear or non-linear, the Singleton bound | ||

1833 | (Section \ref{cedc0:scob0:rbc0:saul0} and Lemma \ref{lem:cedc0:slco0:spcd0:03}) | ||

1834 | assures us that $n-k$ check bits cannot always detect a burst error of | ||

1835 | $n-k+1$ bits. This is an upper limit that cannot be violated. | ||

1836 | |||

1837 | However, intuitively, it seems plausible that $n-k$ check bits could detect a | ||

1838 | burst error of length $n-k$. Imagine that the burst error occurs within a span of | ||

1839 | $n-k$ bits among the $k$ data bits. If each of the $2^{n-k}$ combinations of the | ||

1840 | $n-k$ bits involved in the burst error maps to a different pattern among the $n-k$ | ||

1841 | check bits, then every burst error of length $n-k$ among the data bits | ||

1842 | would be detectable. Intuitively, a one-to-one mapping seems to be the criterion | ||

1843 | for detection of a burst error of length $n-k$. | ||

1844 | |||

1845 | For a linear code, the necessary condition for detection of a burst error | ||

1846 | of length $n-k$ comes directly from Lemma | ||

1847 | \ref{lem:cedc0:sfft0:rmc0:01}, and we present this necessary condition as the | ||

1848 | following lemma. | ||

1849 | |||

1850 | \begin{vworklemmastatement} | ||

1851 | \label{lem:cedc0:slco0:spcb0:01} | ||

1852 | A code can detect burst errors of length $b$ iff every $b$ contiguous | ||

1853 | columns from the code's parity check matrix $H$ are linearly independent. | ||

1854 | (For a code to detect burst errors of length $n-k$, any $n-k$ contiguous | ||

1855 | columns from the code's parity check matrix must form a full-rank matrix.) | ||

1856 | \end{vworklemmastatement} | ||

1857 | \begin{vworklemmaproof} | ||

1858 | Assume a codeword $c$ in the code $C$: then $Hc^T=\mathbf{0}$. | ||

1859 | We desire to introduce a burst error of length $b$ into $c$, and we can | ||

1860 | do this by summing an error vector $e$ with $c$, with the understanding that | ||

1861 | $e$ may contain 1's only in the range of columns corresponding to the burst | ||

1862 | error and 0's everywhere else. In order for the burst error to be undetected, we | ||

1863 | require $H(c \oplus e)^T=\mathbf{0}$, or equivalently that | ||

1864 | $He^T=\mathbf{0}$. In order for $He^T=\mathbf{0}$, either | ||

1865 | $e = \mathbf{0}$ or else the columns of $H$ corresponding to the | ||

1866 | 1's in $e$ are linearly dependent and can sum to $\mathbf{0}$. | ||

1867 | The case of $e=\mathbf{0}$ corresponds to no error, and the case | ||

1868 | of $e \neq \mathbf{0}$ but $He^T=\mathbf{0}$ can happen only if | ||

1869 | $b$ contiguous columns of $H$ corresponding to the location of the burst error | ||

1870 | are not linearly independent. | ||

1871 | \end{vworklemmaproof} | ||

1872 | \vworklemmafooter{} | ||

1873 | |||

1874 | |||

1875 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1876 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1877 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1878 | \subsection{Automatic Generation Of The Parity Check Matrix} | ||

1879 | \label{cedc0:slco0:sagp0} | ||

1880 | |||

1881 | |||

1882 | |||

1883 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1884 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1885 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1886 | \section{Hamming Codes} | ||

1887 | %Section tag: hco0 | ||

1888 | \label{cedc0:shco0} | ||

1889 | |||

1890 | \index{Hamming code}\emph{Hamming codes} are a family of $\hat{d}=3$ (double | ||

1891 | error detecting, single error correcting) codes which were discovered/developed | ||

1892 | by Hamming. | ||

1893 | |||

1894 | Consider the code represented by the parity check matrix | ||

1895 | |||

1896 | \begin{equation} | ||

1897 | \label{eq:cedc0:shco0:01} | ||

1898 | H = \left[ | ||

1899 | \begin{array}{ccccccc} | ||

1900 | 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ | ||

1901 | 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ | ||

1902 | 0 & 0 & 0 & 1 & 1 & 1 & 1 | ||

1903 | \end{array} | ||

1904 | \right] , | ||

1905 | \end{equation} | ||

1906 | |||

1907 | \noindent{}which is known as the Hamming $(7, 4)$ code. Notice that | ||

1908 | the columns of $H$, if one considers the first row the least significant bit, are the | ||

1909 | binary equivalents of the integers 1 through 7, arranged in order from left to right. Notice | ||

1910 | also that $H$ is not in standard form | ||

1911 | suggested by | ||

1912 | (\ref{eq:cedc0:slco0:spcm0:06}), although the columns can be rearranged to | ||

1913 | place it in standard form. | ||

1914 | |||

1915 | One interesting feature of the code suggested by (\ref{eq:cedc0:shco0:01}) | ||

1916 | is when one considers the syndrome of a received message $m$, $syn(m) = Hm^T$. | ||

1917 | If the message is received correctly, $syn(m) = Hm^T = \mathbf{0}$. If the | ||

1918 | message is received with one corrupted bit, the syndrome will give the ordinal | ||

1919 | index of the corrupted bit: for example, a message with the third bit corrupted will | ||

1920 | generate a syndrome of $\left[\begin{array}{c}1\\1\\0\end{array}\right]$, which is the | ||

1921 | third column of $H$ and is the binary representation of 3 (and this leads to | ||

1922 | convenient correction either in digital logic or in software). A message with two bits | ||

1923 | corrupted will always represent a detectable corruption, but would be corrected | ||

1924 | erroneously. A message with three or more corrupted bits may or may not be | ||

1925 | detected and | ||

1926 | can never be corrected. Specifically note that an error involving 3 or more bits | ||

1927 | will not be detected if the sum of the columns of $H$ corresponding to the errors | ||

1928 | is $\mathbf{0}$. | ||

1929 | |||

1930 | However, by far the most interesting feature of the code suggested by | ||

1931 | (\ref{eq:cedc0:shco0:01}) is that it provides a ``formula'' or ``pattern'' | ||

1932 | approach for the construction of a code with $\hat{d}=3$. Note that | ||

1933 | the code can be scaled up by choosing an $H$ with $i$ rows and populating | ||

1934 | it with columns containing the binary representations of the integers | ||

1935 | from 1 through $2^i - 1$, in order. The code suggested by (\ref{eq:cedc0:shco0:01}) | ||

1936 | gives a pattern for the construction of a $(2^i - 1, 2^i - i - 1, 3)$ code | ||

1937 | with as large a length as desired. | ||

1938 | |||

1939 | The Hamming codes with $\hat{d}=3$ represent the codes with the largest $\hat{d}$ that | ||

1940 | can be constructed without more sophisticated mathematical tools. We | ||

1941 | develop these tools in Sections \ref{cedc0:sfft1} and | ||

1942 | \ref{cedc0:scco0}. | ||

1943 | |||

1944 | Hamming codes are perfect codes. If $i \in \vworkintsetpos$ is a parameter, | ||

1945 | choose $n=2^i - 1$ and $k = 2^n - n - 1$ to form an | ||

1946 | $(n,k,3) = (2^i - 1, 2^i - i - 1, 3)$ Hamming code. In order to give | ||

1947 | a minimum Hamming distance $\hat{d}$ of 3, we require a packing radius $\rho$ of | ||

1948 | 1. The number of messages per packing sphere multiplied by the number of codewords gives the | ||

1949 | total number of messages, i.e. | ||

1950 | |||

1951 | \begin{equation} | ||

1952 | \label{eq:cedc0:shco0:02} | ||

1953 | \left[ \left(\begin{array}{c}2^i - 1\\0\end{array}\right) | ||

1954 | + \left(\begin{array}{c}2^i - 1\\1\end{array}\right) \right] | ||

1955 | 2^{2^i-i-1} = 2^{2^i-1}, | ||

1956 | \end{equation} | ||

1957 | |||

1958 | \noindent{}which the reader is encouraged to verify (Exercise \ref{exe:cedc0:sexe0:02}). | ||

1959 | |||

1960 | The observation that Hamming codes exists for all values of the parameter | ||

1961 | $i \in \vworkintsetpos$ and are perfect codes leads to a very easy-to-remember | ||

1962 | rule of thumb which we present as a lemma. | ||

1963 | |||

1964 | \begin{vworklemmastatement} | ||

1965 | \label{lem:cedc0:shco0:01} | ||

1966 | A block of $n=2^i$ requires $n-k=i+1$ check bits to protect at $\hat{d}=3$. | ||

1967 | \end{vworklemmastatement} | ||

1968 | \begin{vworklemmaproof} | ||

1969 | A block of $n=2^i-1$ bits requires $n-k=i$ check bits to protect at $\hat{d}=3$, and | ||

1970 | can be protected with a perfect Hamming code. At $n=2^i$ bits, $i$ check bits | ||

1971 | are no longer adequate, because the code at $n=2^i-1$ is a perfect code and all | ||

1972 | messages are consumed by the necessary packing space; thus at least $i+1$ check bits | ||

1973 | are required. However, $i+1$ check bits will protect $n=2^{i+1}-1$ bits using a | ||

1974 | perfect Hamming code, so $i+1$ bits are enough to protect $n=2^i$ bits. | ||

1975 | \end{vworklemmaproof} | ||

1976 | \vworklemmafooter{} | ||

1977 | |||

1978 | We illustrate the application of Lemma \ref{lem:cedc0:shco0:01} with the following | ||

1979 | example. | ||

1980 | |||

1981 | \begin{vworkexamplestatement} | ||

1982 | \label{ex:cedc0:shco0:01} | ||

1983 | Estimate the number of check bits required | ||

1984 | to protect a 128K ROM at $\hat{d}=3$. | ||

1985 | \end{vworkexamplestatement} | ||

1986 | \begin{vworkexampleparsection}{Solution} | ||

1987 | 128K $=2^{17}$ bytes $=2^{20}$ bits, thus $n=2^i=2^{20}$ in applying | ||

1988 | Lemma \ref{lem:cedc0:shco0:01}. $i+1=21$ check bits are required to protect | ||

1989 | the ROM at $\hat{d}=3$ (although there may be practical reasons for using more check bits). | ||

1990 | \end{vworkexampleparsection} | ||

1991 | \vworkexamplefooter{} | ||

1992 | |||

1993 | |||

1994 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1995 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1996 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

1997 | \section{Finite Field Theory Applied To Polynomials} | ||

1998 | %Section tag: fft1 | ||

1999 | \label{cedc0:sfft1} | ||

2000 | |||

2001 | |||

2002 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2003 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2004 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2005 | \section{Cyclic Codes} | ||

2006 | %Section tag: cco0 | ||

2007 | \label{cedc0:scco0} | ||

2008 | |||

2009 | Cyclic codes are the workhorses of linear codes, and are the codes used | ||

2010 | most often in practice. Cyclic codes are attractive because: | ||

2011 | |||

2012 | \begin{itemize} | ||

2013 | \item Mathematically, they are best understood. | ||

2014 | \item They have a convenient implementation in digital logic using shift | ||

2015 | registers (which can be mimicked in software, but not especially | ||

2016 | efficiently). | ||

2017 | \end{itemize} | ||

2018 | |||

2019 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2020 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2021 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2022 | \subsection{Definition And Properties Of Cyclic Codes} | ||

2023 | %Subsection tag: dpo0 | ||

2024 | \label{cedc0:scco0:sdpo0} | ||

2025 | |||

2026 | The discussion of cyclic codes necessarily entails polynomial math, and | ||

2027 | it is most convenient to think of the terms of a polynomial arranged with | ||

2028 | the highest-order term first (and to think of the ``leftmost'' part of | ||

2029 | a message as being transmitted first). For this reason, for the discussion of cyclic | ||

2030 | codes, we prefer to think of a message as an ordered collection of bits | ||

2031 | |||

2032 | \begin{equation} | ||

2033 | \label{eq:cedc0:scco0:sdpo0:a01} | ||

2034 | [m_{n-1}, m_{n-2}, \ldots{}, m_{0}] | ||

2035 | \end{equation} | ||

2036 | |||

2037 | \noindent{}rather than the ordered collection given in (\ref{eq:cedc0:scon0:sccb0:01}). | ||

2038 | Similarly, we may also use the following notations for messages | ||

2039 | |||

2040 | \begin{eqnarray} | ||

2041 | \label{eq:cedc0:scco0:sdpo0:a02} | ||

2042 | & [d_{k-1}, d_{k-2}, \ldots{}, d_{0}, c_{n-k-1}, c_{n-k-2}, \ldots{}, c_{0}] & \\ | ||

2043 | \label{eq:cedc0:scco0:sdpo0:a02b} | ||

2044 | & [d_{k-1}, d_{k-2}, \ldots{}, d_{0}] | [c_{n-k-1}, c_{n-k-2}, \ldots{}, c_{0}] & | ||

2045 | \end{eqnarray} | ||

2046 | |||

2047 | \noindent{}rather than the notations given in (\ref{eq:cedc0:scon0:sccb0:02}) | ||

2048 | and (\ref{eq:cedc0:scon0:sccb0:02b}). Figure \ref{fig:cedc0:scon0:sccb0:01} | ||

2049 | graphically illustrates this notation with bit nomenclature reversed. | ||

2050 | |||

2051 | \begin{figure} | ||

2052 | \centering | ||

2053 | \includegraphics[width=4.6in]{c_edc0/cword02.eps} | ||

2054 | \caption{Message Consisting Of The Concatenation Of $k$ Data Bits And $n-k$ | ||

2055 | Check Bits, With Bit Notational Conventions For Cyclic Code Discusssion} | ||

2056 | \label{fig:cedc0:scon0:sdpo0:01} | ||

2057 | \end{figure} | ||

2058 | |||

2059 | A \index{cyclic code}\emph{cyclic code} is a linear code such that whenever | ||

2060 | the vector $[m_0 \; m_1 \; m_2 \; \ldots{} \; m_{n-1}]$ is in the code, | ||

2061 | $[m_1 \; m_2 \; m_3 \; \ldots{} \; m_0]$ is also in the code. When | ||

2062 | this definition is applied recursively, it means that for any codeword, all | ||

2063 | cyclic shifts of the codeword are also in the code (that is, in fact, why | ||

2064 | a \emph{cyclic} code is called a \emph{cyclic} code). For example, if | ||

2065 | 10001 is a codeword; then 00011, 00110, 01100, and 11000 must also be | ||

2066 | codewords (notice that these last four codewords are left cyclic shifts of the | ||

2067 | first codeword). Note that since the code is linear, all sums of codewords | ||

2068 | must also be codewords. | ||

2069 | |||

2070 | A cyclic code is characterized by a generator polynomial, which we call | ||

2071 | $g(x)$, of the form | ||

2072 | |||

2073 | \begin{equation} | ||

2074 | \label{eq:cedc0:scco0:sdpo0:01} | ||

2075 | g(x) = g_{n-k} x_{n-k} + g_{n-k-1} x_{n-k-1} + \; \ldots \; + g_1 x + g_0, | ||

2076 | \end{equation} | ||

2077 | |||

2078 | \noindent{}a polynomial of degree $n-k$, naturally containing up to $n-k+1$ terms. | ||

2079 | Each coefficient $g_{n-k} \ldots g_{0}$ is chosen from $GF(2)$, so that | ||

2080 | $g_{n-k} \ldots g_{0} \in \mathbb{B} = \{ 0 , 1 \}$. We assume that | ||

2081 | $g_{n-k}$ and $g_{0}$ are both 1. We explain how the generator polynomial | ||

2082 | specifies the code beginning in Section \ref{cedc0:scco0:ssut0}. | ||

2083 | |||

2084 | Cyclic codes are harnessed in two distinct ways, which we will call | ||

2085 | the \emph{strong} and \emph{weak} ways. | ||

2086 | |||

2087 | In \emph{strong} utilization of cyclic codes | ||

2088 | (Section \ref{cedc0:scco0:ssut0}), we must choose $g(x)$ in a very | ||

2089 | special way with respect to $n$, and we cannot increase | ||

2090 | $n$ arbitrarily (i.e. we are confined to messages of $n$ or | ||

2091 | fewer bits). If we choose $g(x)$ in this way, we can | ||

2092 | control the minimum Hamming distance $\hat{d}$ of the cyclic code we specify. | ||

2093 | We call this utilization \emph{strong} because we are able to preserve a | ||

2094 | strong property, the minimum Hamming distance $\hat{d}$ of the resulting code | ||

2095 | (this is a very desirable feature, as it is in general not easy to construct a code | ||

2096 | with a desirable large $\hat{d}$, and the theory of cyclic codes provides a way to do | ||

2097 | this). | ||

2098 | A typical ``strong'' utilization of a cyclic code may be in a communication peripheral | ||

2099 | which can only accomodate a message of maximum length $\leq n$, and in this case | ||

2100 | we can preserve strong properties of the cyclic code. | ||

2101 | |||

2102 | In \emph{weak} utilization of cyclic codes | ||

2103 | (Section \ref{cedc0:scco0:swut0}), $n$ is unconstrained, and the minimum Hamming | ||

2104 | distance of the code may degrade as far as $\hat{d}=2$ as $n$ is | ||

2105 | increased. We call such a utilization | ||

2106 | \emph{weak} because only a \emph{weak} set of desirable properties can be preserved | ||

2107 | in the resulting code. A typical example of a weak utilization would be the CRC-32 (a | ||

2108 | 32-bit checksum) used to signature large files. Such a utilization usually cannot | ||

2109 | achieve even $\hat{d} = 3$, but can still preserve a low probability of undetected corruption | ||

2110 | and protection against certain types of burst errors. | ||

2111 | |||

2112 | Note that the choice of generator polynomial $g(x)$ | ||

2113 | affects the properties of the code in both | ||

2114 | the strong and weak utilizations, but in different ways. | ||

2115 | |||

2116 | |||

2117 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2118 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2119 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2120 | \subsection{\emph{Strong} Utilization Of Cyclic Codes} | ||

2121 | %Subsection tag: sut0 | ||

2122 | \label{cedc0:scco0:ssut0} | ||

2123 | |||

2124 | In the strong utilization of a cyclic code, | ||

2125 | the vector corresponding to the generator polynomial $g(x)$, | ||

2126 | $[0 \; \ldots \; 0 \; g_{n-k} \; g_{n-k-1} \; \ldots \; g_{0}]$ must | ||

2127 | be in the code, as must all of its cyclic shifts and sums of its | ||

2128 | cyclic shifts. A generator | ||

2129 | matrix (not in standard form, and of course not the only generator | ||

2130 | matrix) for a cyclic code is of the form | ||

2131 | |||

2132 | \begin{equation} | ||

2133 | \label{eq:cedc0:scco0:ssut0:02} | ||

2134 | G = \left[ | ||

2135 | \begin{array}{lllllllll} | ||

2136 | g_{n-k} & g_{n-k-1} & g_{n-k-2} & \cdots & g_{0} & 0 & 0 & \cdots{} & 0 \\ | ||

2137 | 0 & g_{n-k} & g_{n-k-1} & \cdots & g_{1} & g_{0} & 0 & \cdots{} & 0 \\ | ||

2138 | 0 & 0 & g_{n-k} & \cdots & g_{2} & g_{1} & g_{0} & \cdots{} & 0 \\ | ||

2139 | \vdots{} & & & & & & & & \\ | ||

2140 | 0 & 0 & 0 & \cdots & & & & \cdots{} & g_{0} | ||

2141 | \end{array} | ||

2142 | \right]_{k \times n} \!\!\!\!\!\!\!\!\!\!. | ||

2143 | \end{equation} | ||

2144 | |||

2145 | \noindent{}Note that the generator matrix in (\ref{eq:cedc0:scco0:ssut0:02}) | ||

2146 | has rows which are cyclic shifts of the coefficients of $g(x)$ (and | ||

2147 | for reasons discussed later, the other cyclic | ||

2148 | shifts are also in the code). Note also that $G$ is a | ||

2149 | $k \times n$ matrix, consistent with (\ref{eq:cedc0:slco0:sgma0:01b}). | ||

2150 | |||

2151 | It is apparent from (\ref{eq:cedc0:scco0:ssut0:02}) that G can be | ||

2152 | transformed into the form of (\ref{eq:cedc0:slco0:sgma0:01}) by | ||

2153 | elementary row operations. Two arguments can be | ||

2154 | made. First, by theorem, the determinant of an upper triangular matrix | ||

2155 | (the first $k$ columns of $G$) is the product of the diagonal elements, | ||

2156 | and since we've assumed $g_0 = g_{n-k} = 1$, this determinant is necessarily 1. | ||

2157 | Since the first $k$ columns of $G$ have full rank, they can be transformed | ||

2158 | into $I_{k \times k}$. Second, it is clear using elementary row operations how | ||

2159 | to transform the first $k$ columns of $G$ into | ||

2160 | $I_{k \times k}$ (Exercise \ref{exe:cedc0:sexe0:03}). | ||

2161 | |||

2162 | \begin{vworkexamplestatement} | ||

2163 | \label{ex:cedc0:scco0:ssut0:01} | ||

2164 | For the $(7,4)$ code characterized by the generator polynomial | ||

2165 | $g(x) = 1 + x + x^3$, form the generator matrix of the code | ||

2166 | as in (\ref{eq:cedc0:scco0:ssut0:02}), reduce it by elementary | ||

2167 | row operations to the form of (\ref{eq:cedc0:slco0:sgma0:01}), | ||

2168 | and enumerate the $2^k = 16$ codewords. | ||

2169 | \end{vworkexamplestatement} | ||

2170 | \begin{vworkexampleparsection}{Solution} | ||

2171 | With generator polynomial $g(x) = 1 + x + x^3$, $g_0 = 0$, $g_1 = 1$, | ||

2172 | $g_2 = 0$, and $g_3 = 1$. By (\ref{eq:cedc0:scco0:ssut0:02}), | ||

2173 | |||

2174 | \begin{equation} | ||

2175 | \label{eq:ex:cedc0:scco0:ssut0:01:01} | ||

2176 | G = \left[ | ||

2177 | \begin{array}{ccccccc} | ||

2178 | g_0 & g_1 & g_2 & g_3 & 0 & 0 & 0 \\ | ||

2179 | 0 & g_0 & g_1 & g_2 & g_3 & 0 & 0 \\ | ||

2180 | 0 & 0 & g_0 & g_1 & g_2 & g_3 & 0 \\ | ||

2181 | 0 & 0 & 0 & g_0 & g_1 & g_2 & g_3 | ||

2182 | \end{array} | ||

2183 | \right] | ||

2184 | = | ||

2185 | \left[ | ||

2186 | \begin{array}{ccccccc} | ||

2187 | 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ | ||

2188 | 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ | ||

2189 | 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ | ||

2190 | 0 & 0 & 0 & 1 & 1 & 0 & 1 | ||

2191 | \end{array} | ||

2192 | \right] . | ||

2193 | \end{equation} | ||

2194 | |||

2195 | Adding (in the sense of $GF(2)$, see Section \ref{cedc0:sfft0:dff0}) | ||

2196 | the second row to the first yields | ||

2197 | |||

2198 | \begin{equation} | ||

2199 | \label{eq:ex:cedc0:scco0:ssut0:01:02} | ||

2200 | G = \left[ | ||

2201 | \begin{array}{ccccccc} | ||

2202 | 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ | ||

2203 | 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ | ||

2204 | 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ | ||

2205 | 0 & 0 & 0 & 1 & 1 & 0 & 1 | ||

2206 | \end{array} | ||

2207 | \right] . | ||

2208 | \end{equation} | ||

2209 | |||

2210 | Adding the third row to the first row and to the second row (two | ||

2211 | row operations) yields | ||

2212 | |||

2213 | \begin{equation} | ||

2214 | \label{eq:ex:cedc0:scco0:ssut0:01:03} | ||

2215 | G = \left[ | ||

2216 | \begin{array}{ccccccc} | ||

2217 | 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ | ||

2218 | 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ | ||

2219 | 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ | ||

2220 | 0 & 0 & 0 & 1 & 1 & 0 & 1 | ||

2221 | \end{array} | ||

2222 | \right] . | ||

2223 | \end{equation} | ||

2224 | |||

2225 | Finally, adding the fourth row to the second row and to the third row (two | ||

2226 | row operations) yields | ||

2227 | |||

2228 | \begin{equation} | ||

2229 | \label{eq:ex:cedc0:scco0:ssut0:01:04} | ||

2230 | G = \left[ | ||

2231 | \begin{array}{ccccccc} | ||

2232 | 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ | ||

2233 | 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ | ||

2234 | 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ | ||

2235 | 0 & 0 & 0 & 1 & 1 & 0 & 1 | ||

2236 | \end{array} | ||

2237 | \right] . | ||

2238 | \end{equation} | ||

2239 | |||

2240 | The $2^4 = 16$ codewords can be enumerated by forming all linear combinations | ||

2241 | of the rows of any of the matrices | ||

2242 | (\ref{eq:ex:cedc0:scco0:ssut0:01:01}) | ||

2243 | through (\ref{eq:ex:cedc0:scco0:ssut0:01:04}). These 16 codewords are | ||

2244 | enumerated in Table \ref{tbl:ex:cedc0:scco0:ssut0:01:01}. | ||

2245 | |||

2246 | \begin{table} | ||

2247 | \caption{$2^4 = 16$ Codewords For Code Of Example \ref{ex:cedc0:scco0:ssut0:01}} | ||

2248 | \label{tbl:ex:cedc0:scco0:ssut0:01:01} | ||

2249 | \begin{center} | ||

2250 | \begin{tabular}{|c|c|} | ||

2251 | \hline | ||

2252 | Data & Codeword \\ | ||

2253 | (Value Of $k$ Data Bits) & \\ | ||

2254 | \hline | ||

2255 | \hline | ||

2256 | 0 & 0000 000 \\ | ||

2257 | \hline | ||

2258 | 1 & 0001 101 \\ | ||

2259 | \hline | ||

2260 | 2 & 0010 111 \\ | ||

2261 | \hline | ||

2262 | 3 & 0011 010 \\ | ||

2263 | \hline | ||

2264 | 4 & 0100 011 \\ | ||

2265 | \hline | ||

2266 | 5 & 0101 110 \\ | ||

2267 | \hline | ||

2268 | 6 & 0110 100 \\ | ||

2269 | \hline | ||

2270 | 7 & 0111 001 \\ | ||

2271 | \hline | ||

2272 | 8 & 1000 110 \\ | ||

2273 | \hline | ||

2274 | 9 & 1001 011 \\ | ||

2275 | \hline | ||

2276 | 10 & 1010 001 \\ | ||

2277 | \hline | ||

2278 | 11 & 1011 100 \\ | ||

2279 | \hline | ||

2280 | 12 & 1100 101 \\ | ||

2281 | \hline | ||

2282 | 13 & 1101 000 \\ | ||

2283 | \hline | ||

2284 | 14 & 1110 010 \\ | ||

2285 | \hline | ||

2286 | 15 & 1111 111 \\ | ||

2287 | \hline | ||

2288 | \end{tabular} | ||

2289 | \end{center} | ||

2290 | \end{table} | ||

2291 | \end{vworkexampleparsection} | ||

2292 | \vworkexamplefooter{} | ||

2293 | |||

2294 | |||

2295 | |||

2296 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2297 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2298 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2299 | \subsection{\emph{Weak} Utilization Of Cyclic Codes} | ||

2300 | %Subsection tag: wut0 | ||

2301 | \label{cedc0:scco0:swut0} | ||

2302 | |||

2303 | |||

2304 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2305 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2306 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2307 | \subsection{Perfect Codes} | ||

2308 | %Subsection tag: pfc0 | ||

2309 | \label{cedc0:scob0:spfc0} | ||

2310 | |||

2311 | We define a \index{perfect code}\emph{perfect code} as a code | ||

2312 | where (\ref{eq:cedc0:scob0:rbc0:shsp0:01}) | ||

2313 | is an equality---that is, where the volume of the $2^k$ packing spheres precisely | ||

2314 | consumes the $2^n$ messages available. A perfect code has no ``waste'': that is, | ||

2315 | there are no messages which do not participate in maintaining the required separation | ||

2316 | between codewords. | ||

2317 | |||

2318 | In this section, we address two issues: | ||

2319 | |||

2320 | \begin{itemize} | ||

2321 | \item The existence of integer solutions to | ||

2322 | |||

2323 | \begin{equation} | ||

2324 | \label{eq:cedc0:scob0:spfc0:01} | ||

2325 | 2^k V(n, \rho) = 2^n , | ||

2326 | \end{equation} | ||

2327 | |||

2328 | which is a question from number theory. | ||

2329 | |||

2330 | \item Given $n$,$k$ which satisfy (\ref{eq:cedc0:scob0:spfc0:01}), the existence | ||

2331 | of the codes whose possible existence is predicted. It should be remembered | ||

2332 | that (\ref{eq:cedc0:scob0:spfc0:01}) is a necessary but not sufficient | ||

2333 | condition. | ||

2334 | \end{itemize} | ||

2335 | |||

2336 | |||

2337 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2338 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2339 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2340 | \subsubsection[Existence Of Integer Solutions To | ||

2341 | \protect\mbox{\protect$2^k V(n, \rho) = 2^n$}] | ||

2342 | {Existence Of Integer Solutions To | ||

2343 | \protect\mbox{\protect\boldmath$2^k V(n, \rho) = 2^n$}} | ||

2344 | %Subsubsection tag: pfc0 | ||

2345 | \label{cedc0:scob0:spfc0:seis0} | ||

2346 | |||

2347 | |||

2348 | |||

2349 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2350 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2351 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2352 | \subsubsection{Existence Of Predicted Perfect Codes} | ||

2353 | %Subsubsection tag: epc0 | ||

2354 | \label{cedc0:scob0:spfc0:sepc0} | ||

2355 | |||

2356 | |||

2357 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2358 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2359 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2360 | \section{Economical Implementation Of Linear Codes In Software} | ||

2361 | %Section tag: eim0 | ||

2362 | \label{cedc0:seim0} | ||

2363 | |||

2364 | |||

2365 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2366 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2367 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2368 | \section[\protect\mbox{\protect$\hat{d}=2$} Codes Useful In Microcontroller Work] | ||

2369 | {\protect\mbox{\protect\boldmath$\hat{d}=2$} Codes Useful In Microcontroller Work} | ||

2370 | %Section tag: dtc0 | ||

2371 | \label{cedc0:sdtc0} | ||

2372 | |||

2373 | |||

2374 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2375 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2376 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2377 | \section[\protect\mbox{\protect$\hat{d}=3$} Codes Useful In Microcontroller Work] | ||

2378 | {\protect\mbox{\protect\boldmath$\hat{d}=3$} Codes Useful In Microcontroller Work} | ||

2379 | %Section tag: dhc0 | ||

2380 | \label{cedc0:sdhc0} | ||

2381 | |||

2382 | |||

2383 | |||

2384 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2385 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2386 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2387 | \section{Acknowledgements} | ||

2388 | \label{cedc0:sack0} | ||

2389 | |||

2390 | I'm very grateful to the following individuals who contributed insight | ||

2391 | about error-detecting and error-correcting | ||

2392 | codes on \index{comp.arch.embedded@\texttt{comp.arch.embedded}}\texttt{comp.arch.embedded} | ||

2393 | and other | ||

2394 | newsgroups: | ||

2395 | Alan Coppola, | ||

2396 | Eric Doenges, | ||

2397 | Glen Herrmannsfeldt, | ||

2398 | Dan Kotlow, | ||

2399 | John Larkin, | ||

2400 | Steven Murray, | ||

2401 | Sphero Pefhany, | ||

2402 | Jan-Hinnerk Reichert, | ||

2403 | Thad Smith, | ||

2404 | and | ||

2405 | Jim Stewart. | ||

2406 | |||

2407 | I'm grateful to | ||

2408 | \index{Sperber, Ron} Ron Sperber \cite{bibref:i:ronsperber} and | ||

2409 | \index{Chapman, Robin} Robin Chapman \cite{bibref:i:robinchapman} | ||

2410 | for assistance with field theory offered on the | ||

2411 | \texttt{sci.math} newsgroup \cite{bibref:n:scimathnewsgroup}. | ||

2412 | |||

2413 | I'm also grateful to Mr. Michael J. Downes of the | ||

2414 | \index{comp.text.tex@\texttt{comp.text.tex}}\texttt{comp.text.tex} | ||

2415 | newsgroup, who assisted me with a technical difficulty involving | ||

2416 | the \LaTeX ``$\backslash$\texttt{protect}'' command. | ||

2417 | |||

2418 | |||

2419 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2420 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2421 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2422 | \section{Exercises} | ||

2423 | \label{cedc0:sexe0} | ||

2424 | |||

2425 | \begin{vworkexercisestatement} | ||

2426 | \label{exe:cedc0:sexe0:01} | ||

2427 | Show that the minimum Hamming distance of the code $\{0001, 0110, 1010, 1101\}$ | ||

2428 | is 2. | ||

2429 | \end{vworkexercisestatement} | ||

2430 | |||

2431 | \begin{vworkexercisestatement} | ||

2432 | \label{exe:cedc0:sexe0:02} | ||

2433 | Verify Equation \ref{eq:cedc0:shco0:02}. | ||

2434 | \end{vworkexercisestatement} | ||

2435 | |||

2436 | \begin{vworkexercisestatement} | ||

2437 | \label{exe:cedc0:sexe0:03} | ||

2438 | Outline a procedure for transforming the $G$ of | ||

2439 | (\ref{eq:cedc0:scco0:sdpo0:02}) into | ||

2440 | the form of (\ref{eq:cedc0:slco0:sgma0:01}). | ||

2441 | \end{vworkexercisestatement} | ||

2442 | \vworkexercisefooter{} | ||

2443 | |||

2444 | \vworkexercisefooter{} | ||

2445 | |||

2446 | |||

2447 | |||

2448 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2449 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2450 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||

2451 | |||

2452 | \noindent\begin{figure}[!b] | ||

2453 | \noindent\rule[-0.25in]{\textwidth}{1pt} | ||

2454 | \begin{tiny} | ||

2455 | \begin{verbatim} | ||

2456 | dashley | 277 | $HeadURL$ |

2457 | $Revision$ | ||

2458 | $Date$ | ||

2459 | $Author$ | ||

2460 | dashley | 140 | \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 |

Name | Value |
---|---|

svn:eol-style |
native |

svn:keywords |
Author Date Id Revision URL Header |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |