Constant-weight code: Difference between revisions

Revision as of 17:04, 13 June 2018

Revision as of 17:11, 13 June 2018

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 -of -''N'' codes ==

{{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 -of -2 code;

[[pulse-position modulation]] uses a 1 -of -''n'' code;

[[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 -of -six]] code;

etc.

== ''m ''-of -''n'' codes==

An '''''m'' -of -''n'' code''' is a separable [[error detection]] code with a code word length of ''n'' bits, where each code word contains exactly ''m'' instances of a "one". A single bit error will cause the code word to have either {{nowrap|''m'' + 1}} or {{Nowrap|''m'' &ndashminus; 1}} "ones". An example ''m''-of-''n'' code is the [[Two-out-of-five code|2 -of -5 code]] used by the [[United States Postal Service]].

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 -of -6 code

|-

! 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 -of -9 code;

[[bi-quinary coded decimal]] code uses a 2 -of -7 code,

the [[Two-out-of-five code|2 -of -5 code]],

etc.