Content deleted Content added
hyphenation etc. |
|||
Line 11:
Constant-weight codes, like [[Berger code]]s, can detect all unidirectional errors.
== ''A''(''n'', ''d'', ''w'') ==
The central problem regarding constant-weight codes is the following: what is the maximum number of codewords in a binary constant-weight code with length <math>n</math>, [[Hamming distance]] <math>d</math>, and weight <math>w</math>? This number is called <math>A(n,d,w)</math>.
Apart from some trivial observations, it is generally impossible to compute these numbers in a straightforward way. Upper bounds are given by several important theorems such as the [[first Johnson bound|first]] and [[second Johnson bound]]s,<ref>See pp. 526–527 of F. J. MacWilliams and N. J. A. Sloane (1979). ''The Theory of Error-Correcting Codes''. Amsterdam: North-Holland.</ref> and better upper bounds can sometimes be found in other ways. Lower bounds are most often found by exhibiting specific codes, either with use of a variety of methods from discrete mathematics, or through heavy computer searching. A large table of such record-breaking codes was published in 1990,<ref name="brouwer">A. E. Brouwer, James B. Shearer, N. J. A. Sloane and Warren D. Smith (1990). "A New Table of Constant Weight Codes". ''IEEE Transactions of Information Theory'' '''36'''.</ref> and an extension to longer codes (but only for those values of <math>d</math> and <math>w</math> which are relevant for the GSM application) was published in 2006.<ref name="smith"/>
== 1
{{main|one-hot}}
A special case of constant weight codes are the one-of-''N'' codes, that encode <math>\log_2 N</math> bits in a code-word of <math>N</math> bits. The one-of-two code uses the code words 01 and 10 to encode the bits '0' and '1'. A one-of-four code can use the words 0001, 0010, 0100, 1000 in order to encode two bits 00, 01, 10, and 11. An example is [[dual rail encoding]], and chain link <ref>{{cite news
| title=System-on-Chip Design using Self-timed Networks-on-Chip
| url=http://www.design-reuse.com/articles/14561/system-on-chip-design-using-self-timed-networks-on-chip.html
Line 28:
Some of the more notable uses of one-hot codes include
[[biphase mark code]] uses a 1
[[pulse-position modulation]] uses a 1
[[address decoder]],
etc.
Line 50:
[[6b/8b encoding]] uses a 4 of 8 code;
the [[Hadamard code]] is a <math>2^k/2</math> of <math>2^k</math> code (except for the zero codeword),
the [[IEEE 1355#Slice: TS-FO-02|three
etc.
== ''m
An '''''m''
The simplest implementation is to append a string of ones to the original data until it contains ''m'' ones, then append zeros to create a code of length ''n''.
Line 62:
{|class="wikitable" style="text-align:center"
|+ 3
|-
! Original 3 data bits !! Appended bits
Line 85:
Some of the more notable uses of constant-weight codes, other than the one-hot and balanced-weight codes already mentioned above, include
[[Code 39]] uses a 3
[[bi-quinary coded decimal]] code uses a 2
the [[Two-out-of-five code|2
etc.
|