Content deleted Content added
→top: hyphenation |
m →top: Add m-out-of-n alias Tags: Mobile edit Mobile app edit Android app edit App section source |
||
| (13 intermediate revisions by 12 users not shown) | |||
Line 1:
{{short description|Method for encoding data in communications}}
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]].▼
{{Use dmy dates|date=May 2019|cs1-dates=y}}
▲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.
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
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.
Line 35 ⟶ 37:
== 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
|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/
|pages=
|accessdate=2018-02-12
|doi=10.1109/jsac.2010.100207
}}</ref> ▼
|s2cid=8596702
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
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==
Line 95 ⟶ 105:
== 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]]
* [http://codes.se/bounds/ Table of upper bounds on <math>A(n,d,w)</math>] maintained by [[Erik Agrell]]
[[Category:Information theory]]
[[Category:Error detection and correction]]
| |||