Constant-weight code: Difference between revisions

Revision as of 02:18, 9 July 2019

Latest revision as of 22:09, 7 April 2025

(9 intermediate revisions by 8 users not shown)

Line 1:

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

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

Line 43:

|title=Very efficient balanced codes

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

|issue=2

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

|pages=188–192

|accessdate=2018-02-12

|doi=10.1109/jsac.2010.100207

|s2cid=8596702

}}</ref>

Line 51 ⟶ 54:

[[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-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==

Line 97 ⟶ 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]] (update of the [http://www.research.att.com/~njas/codes/Andw/index.html earlier table] by [[Neil Sloane]] and [[E. M. Rains]])

* [http://codes.se/bounds/ Table of upper bounds on <math>A(n,d,w)</math>] maintained by [[Erik Agrell]]