Constant-weight code: Difference between revisions

Revision as of 15:04, 5 March 2010

Latest revision as of 22:09, 7 April 2025

(38 intermediate revisions by 23 users not shown)

Line 1:

{{short description|Method for encoding data in communications}}

{{Mergefrom|M of n codes|discuss=Talk:M of n codes|date=April 2008}}

{{Use dmy dates|date=May 2019|cs1-dates=y}}

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 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.

In [[coding theory]], a '''constant-weight code''', also called an '''''m''-of-''n'' code''' or '''''m''-out-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.

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 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.<ref name="smith">D. H. Smith, L. A. Hughes and S. Perkins (2006). "[http://www.combinatorics.org/Volume_13/Abstracts/v13i1a2.html A New Table of Constant Weight Codes of Length Greater than 28]". ''The Electronic Journal of Combinatorics'' '''13'''.</ref>

Most [[barcode]]s use a binary constant-weight code to simplify automatically setting the brightness threshold that distinguishes black and white stripes.

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 bounds''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'. aA 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 articlenews

| title=System-on-Chip Design using Self-timed Networks-on-Chip

| url=http://www.silistixdesign-reuse.com/membersarticles/privatePapers14561/designwave2system-on-chip-design-using-self-timed-networks-on-chip.pdfhtml

| coauthorsauthor=W.J. Bainbridge, A.Bardsley, R.W.McGuffin

| author2=A. Bardsley

}}</ref>used in delay insensitive circuits.

| author3=R.W. McGuffin

}}</ref> 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]];<ref name="knuth">{{cite journal|author=D.E. Knuth|title=Efficient balanced codes|journal=IEEE Transactions on Information Theory|volume=32|issue=1|pages=51–53|date=January 1986|doi=10.1109/TIT.1986.1057136|url=http://www.costasarrays.org/costasrefs/knuth86efficient.pdf}}{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> 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.<ref name="knuth"/><ref name="optimal">{{cite journal|author1=Sulaiman Al-Bassam|author2=Bella Bose|title=On Balanced Codes|journal=IEEE Transactions on Information Theory|volume=36|issue=2|pages=406–408|date=March 1990|doi=10.1109/18.52490}}</ref><ref>{{Cite journal

|journal= IEEE Journal on Selected Areas in Communications

|volume=28

|date=2010

|title=Very efficient balanced codes

|author=[[Kees Schouhamer Immink|K. Schouhamer Immink]] and J. Weber

|issue=2

|url=https://www.researchgate.net/publication/224110287

|pages=188–192

|accessdate=2018-02-12

|doi=10.1109/jsac.2010.100207

|s2cid=8596702

}}</ref>

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-1}</math> of <math>2^k</math> code (except for the zero codeword),

the [[IEEE 1355#Slice: TS-FO-02|three-of-six]] code;

etc.

The 3-wire lane encoding used in [[MIPI Alliance | MIPI]] C-PHY can be considered a generalization of constant-weight code to ternary -- each wire transmits a [[ternary signal]], and at any one instant one of the 3 wires is transmitting a low, one is transmitting a middle, and one is transmitting a high signal.<ref>

[https://www.design-reuse.com/articles/43954/demystifying-mipi-c-phy-dphy-subsystem.html "Demystifying MIPI C-PHY / DPHY Subsystem - Tradeoffs, Challenges, and Adoption"]

([https://www.chipestimate.com/Demystifying-MIPI-C-PHY--DPHY-Subsystem-Tradeoffs-Challenges-and-Adoption-/Mixel/Technical-Article/2018/04/24 mirror])

</ref>

== ''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'' &minus; 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.

== References ==

<!--See http://en.wikipedia.org/wiki/Wikipedia:Footnotes for an explanation of how to generate footnotes using the <ref> and </ref> tags and the tag below -->

{{reflist}}

<references/>

== External links ==

* [http://www.win.tue.nl/~aeb/codes/Andw.html Table of lower bounds on <math>A(n,d,w)</math>] maintained by [[Andries Brouwer]] (update of the [http://www.research.att.com/~njas/codes/Andw/index.html earlier table] by [[Neil Sloane]] and [[E. M. Rains]])

* [http://webfiles.portal.chalmerscodes.se/s2/research/kit/bounds/ Table of upper bounds on <math>A(n,d,w)</math>] maintained by [[Erik Agrell]]

[[Category:Information theory]]