Error Detecting and Error Correcting Codes
Bell System Technical Journal, 1950 · paper · Computer science
Studies binary systematic codes that detect and correct errors, motivated by the need for large computing machines to run without a single error. It examines redundancy as the cost of this protection.
1 finding
Wording The triangle inequality is printed as "D(z, y) + D(y, z) ≥ D(x, z) (triangle inequality)"; it should read D(x, y) + D(y, z) ≥ D(x, z).
- p. 9 Section 5, metric conditions, third line
D(y, z) ≥ D(x, z) (triangle inequality)
- p. 9 Section 5, display of metric axioms, third line
D(z, y) + D(y, z) ≥ D(x, z) (triangle inequality)
Only the authors can say what is right here.
Judge's note: In the page 9 image, the first argument of the first term in the third metric condition looks like z, not the x used on the line above. As printed, the left-hand side does not involve x, so the inequality is not the triangle inequality. The scan resolution is limited and the text layer is garbled ("Dt», y)"), so the authors or the original print should confirm the glyph. The first quoted fragment, "D(y, z) ≥ D(x, z)", is only a partial quote of the same line.
Second check: another model agreed
Report a problem with this finding
6 minor (typos and the like; most checked by the judge only)
Wording k is defined as the number of check positions ("k = n - m digits are used for error detection and correction") but Section 8 reuses it as a distance parameter ("minimum distance of 2k - 1 ... 2k") and Section 9 uses it in C(n, k) and B(n, 2k - 1) = 2^m ≤ 2^n/(1 + C(n,1) + ... + C(n, k - 1)), without redefinition.
- p. 2 Introduction, definition of systematic codes
k = n - m digits are used for error detection and correction
- p. 12 Section 8, general theorem
distance of 2k - 1 there corresponds a minimum redundancy code of N
- p. 13 Section 9
where C(n, k) is the binomial coefficient
Judge's note: Checked pages 2, 12 and 13. On p.12 k is clearly a distance parameter, and on p.13 the summary formula prints it next to m (the number of information positions), where it no longer means n - m. The notation is ambiguous but the mathematics can be recovered from context, so this is a minor notational point.
Second check: another model agreed
Report a problem with this finding
Wording "Two parity checks can at most locate four positions" (p.14) does not match Section 3's rule that the checking number must also encode "the zero value meaning no error". Under that rule, two checks can distinguish at most three error positions.
- p. 14 Section 9, after the non-systematic code example
Two parity checks can at most locate four positions
- p. 4 Section 3
with the zero value meaning no error in the symbol
Only the authors can say what is right here.
Judge's note: Checked the page 14 and page 4 images. Section 3 reserves the zero checking number for 'no error', which gives 2^k ≥ n + 1. With k = 2 that leaves 3 nonzero values. The text says four. The conclusion that two checks cannot locate a single error among six positions holds under either count. The authors should say whether 'four' was meant to count all checking-number values.
Second check: another model agreed
Report a problem with this finding
Wording A sphere is defined as "all points which are at a distance r from the point x" (the surface only), but later counts treat it as a ball: "a center point and n points on its surface, a total of n + 1 points" and "Each sphere will contain 1 + C(n, 1) + C(n, 2) points".
- p. 9 Section 5, definition of sphere
is defined as all points which are at a distance r from the point x
- p. 11 Section 7, last line
Each sphere has a center point and
- p. 13 Section 9, first paragraph
Each sphere will contain
- p. 12 Section 7, sphere-packing count
a total of n + 1 points
Judge's note: Checked pages 9, 11, 12 and 13. Page 9 defines the sphere as the points at exactly distance r and speaks of points on its "surface". Sections 7 and 9 count the centre and all points within distance r, which is what the packing bounds require. The author's intent is clear from the word "surface", but the formal definition does not match how it is used.
Second check: another model agreed
Report a problem with this finding
Typo The term is defined in italics as "checking number", but the next sentence says "Thus the check number must describe m + k + 1 different things".
- p. 4 Section 3, end of second paragraph
Thus the check number must describe m + k + 1 different things
Judge's note: The page 4 image confirms that the italic term "checking number" is followed by "check number" in the next sentence. The meaning is clear, so this is only a cosmetic inconsistency in terminology.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling: "was of mini-mum reduncancy" should read "redundancy".
- p. 12 Section 8, end of first paragraph
mum reduncancy. Thus the codes of section 4 are of minimum redundancy.
- p. 12 Section 8, first paragraph
mum reduncancy
- p. 12
mum reduncancy. Thus the codes of section 4
Judge's note: The page 12 image (Section 8, first paragraph) shows "reduncancy". The next sentence spells "redundancy" correctly.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling: "methods have yet been found for contructing optimal codes" should read "constructing".
- p. 13 Section 9, last paragraph
methods have yet been found for contructing optimal codes
- p. 13 Section 9, last paragraph
contructing optimal codes
Judge's note: The page 13 image (last paragraph of Section 9) shows "contructing".
Second check: none (judge only)