Admin: Created page with "In coding theory, a '''constant-weight code''', also called an '''m of n code''', is an error detection and correction code where all codewords share the same Hammin..."

2019-05-04T02:30:09Z

Created page with "In coding theory, a '''constant-weight code''', also called an '''m of n code''', is an error detection and correction code where all codewords share the same Hammin..."

New page

In [[coding theory]], a '''constant-weight code''', also called an '''m of n code''', is an [[error detection and correction]] code where all codewords share the same [[Hamming weight]].
The [[one-hot]] code and the '''balanced code''' are two widely used kinds of constant-weight code.

The theory is closely connected to that of [[Combinatorial design|designs]] (such as [[block design|''t''-design]]s and [[Steiner system]]s). Most of the work on this very vital field of [[discrete mathematics]] is concerned with ''binary'' constant-weight codes.

Binary constant-weight codes have several applications, including [[Frequency-hopping spread spectrum|frequency hopping]] in [[Global System for Mobile Communications|GSM]] networks.
Most [[barcode]]s use a binary constant-weight code to simplify automatically setting the threshold.
Most [[line code]]s use either a constant-weight code, or a nearly-constant-weight [[paired disparity code]].
In addition to use as error correction codes, the large space between code words can also be used in the design of [[asynchronous circuit]]s such as [[delay insensitive circuit]]s.

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, 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, 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. used in delay insensitive circuits. For these codes, <math>n=N,~ d=2,~ w=1</math> and <math>A(n, d, w) = n</math>.

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.

== Balanced code ==

In [[coding theory]], a '''balanced code''' is a [[binary numeral system|binary]] [[forward error correction]] code for which each codeword contains an equal number of zero and one bits. Balanced codes have been introduced by [[Donald Knuth]]; they are a subset of so-called unordered codes, which are codes having the property that the positions of ones in a codeword are never a subset of the positions of the ones in another codeword. Like all unordered codes, balanced codes are suitable for the detection of all [[unidirectional error]]s in an encoded message. Balanced codes allow for particularly efficient decoding, which can be carried out in parallel.

Some of the more notable uses of balanced-weight codes include
[[biphase mark code]] uses a 1 of 2 code;
[[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 ''m'' + 1 or ''m'' – 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''.

Example:

{|class="wikitable" style="text-align:center"
|+ 3 of 6 code
|-
! Original 3 data bits !! Appended bits
|-
|000 || 111
|-
|001 || 110
|-
|010 || 110
|-
|011 || 100
|-
|100 || 110
|-
|101 || 100
|-
|110 || 100
|-
|111 || 000
|-
|}

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.

==Source==

[http://wikipedia.org/ http://wikipedia.org/]
[[Category:Error-correcting codes]]
==See Also on BitcoinWiki==
* [[Agrolot]]
* [[Coinnup]]
* [[Narrative]]
* [[Skillchain]]
* [[WULET]]

Constant-weight code - Revision history

Admin: Created page with "In coding theory, a '''constant-weight code''', also called an '''m of n code''', is an error detection and correction code where all codewords share the same Hammin..."