# Constant-weight code > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Constant-weight_code > Markdown URL: https://mediated.wiki/source/Constant-weight_code.md > Source: https://en.wikipedia.org/wiki/Constant-weight_code > Source revision: 1284488701 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Method for encoding data in communications In [coding theory](/source/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](/source/Error_detection_and_correction) code where all codewords share the same [Hamming weight](/source/Hamming_weight). The [one-hot](/source/One-hot) code and the **balanced code** are two widely used kinds of constant-weight code. The theory is closely connected to that of [designs](/source/Combinatorial_design) (such as [*t*-designs](/source/Block_design) and [Steiner systems](/source/Steiner_system)). Most of the work on this field of [discrete mathematics](/source/Discrete_mathematics) is concerned with *binary* constant-weight codes. Binary constant-weight codes have several applications, including [frequency hopping](/source/Frequency-hopping_spread_spectrum) in [GSM](/source/Global_System_for_Mobile_Communications) networks.[1] Most [barcodes](/source/Barcode) use a binary constant-weight code to simplify automatically setting the brightness threshold that distinguishes black and white stripes. Most [line codes](/source/Line_code) use either a constant-weight code, or a nearly-constant-weight [paired disparity code](/source/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 circuits](/source/Asynchronous_circuit) such as [delay insensitive circuits](/source/Delay_insensitive_circuit). Constant-weight codes, like [Berger codes](/source/Berger_code), 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 n {\displaystyle n} , [Hamming distance](/source/Hamming_distance) d {\displaystyle d} , and weight w {\displaystyle w} ? This number is called A ( n , d , w ) {\displaystyle A(n,d,w)} . 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](/source/First_Johnson_bound) and [second Johnson bounds](/source/Second_Johnson_bound),[2] 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,[3] and an extension to longer codes (but only for those values of d {\displaystyle d} and w {\displaystyle w} which are relevant for the GSM application) was published in 2006.[1] ## 1-of-*N* codes Main article: [one-hot](/source/One-hot) A special case of constant weight codes are the one-of-*N* codes, that encode log 2 ⁡ N {\displaystyle \log _{2}N} bits in a code-word of N {\displaystyle N} 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](https://en.wikipedia.org/w/index.php?title=Dual_rail_encoding&action=edit&redlink=1), and chain link [4] used in delay insensitive circuits. For these codes, n = N , d = 2 , w = 1 {\displaystyle n=N,~d=2,~w=1} and A ( n , d , w ) = n {\displaystyle A(n,d,w)=n} . Some of the more notable uses of one-hot codes include [biphase mark code](/source/Biphase_mark_code) uses a 1-of-2 code; [pulse-position modulation](/source/Pulse-position_modulation) uses a 1-of-*n* code; [address decoder](/source/Address_decoder), etc. ## Balanced code In [coding theory](/source/Coding_theory), a **balanced code** is a [binary](/source/Binary_numeral_system) [forward error correction](/source/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](/source/Donald_Knuth);[5] 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 errors](/source/Unidirectional_error) in an encoded message. Balanced codes allow for particularly efficient decoding, which can be carried out in parallel.[5][6][7] Some of the more notable uses of balanced-weight codes include [biphase mark code](/source/Biphase_mark_code) uses a 1 of 2 code; [6b/8b encoding](/source/6b%2F8b_encoding) uses a 4 of 8 code; the [Hadamard code](/source/Hadamard_code) is a 2 k − 1 {\displaystyle 2^{k-1}} of 2 k {\displaystyle 2^{k}} code (except for the zero codeword), the [three-of-six](/source/IEEE_1355#Slice:_TS-FO-02) code; etc. The 3-wire lane encoding used in [MIPI](/source/MIPI_Alliance) C-PHY can be considered a generalization of constant-weight code to ternary -- each wire transmits a [ternary signal](/source/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.[8] ## *m*-of-*n* codes An ***m*-of-*n* code** is a separable [error detection](/source/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 [2-of-5 code](/source/Two-out-of-five_code) used by the [United States Postal Service](/source/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: 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](/source/Code_39) uses a 3-of-9 code; [bi-quinary coded decimal](/source/Bi-quinary_coded_decimal) code uses a 2-of-7 code, the [2-of-5 code](/source/Two-out-of-five_code), etc. ## References 1. ^ [***a***](#cite_ref-smith_1-0) [***b***](#cite_ref-smith_1-1) D. H. Smith, L. A. Hughes and S. Perkins (2006). "[A New Table of Constant Weight Codes of Length Greater than 28](http://www.combinatorics.org/Volume_13/Abstracts/v13i1a2.html)". *The Electronic Journal of Combinatorics* **13**. 1. **[^](#cite_ref-2)** See pp. 526–527 of F. J. MacWilliams and N. J. A. Sloane (1979). *The Theory of Error-Correcting Codes*. Amsterdam: North-Holland. 1. **[^](#cite_ref-brouwer_3-0)** 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**. 1. **[^](#cite_ref-4)** W.J. Bainbridge; A. Bardsley; R.W. McGuffin. ["System-on-Chip Design using Self-timed Networks-on-Chip"](http://www.design-reuse.com/articles/14561/system-on-chip-design-using-self-timed-networks-on-chip.html). 1. ^ [***a***](#cite_ref-knuth_5-0) [***b***](#cite_ref-knuth_5-1) D.E. Knuth (January 1986). ["Efficient balanced codes"](http://www.costasarrays.org/costasrefs/knuth86efficient.pdf) (PDF). *IEEE Transactions on Information Theory*. **32** (1): 51–53. [doi](/source/Doi_(identifier)):[10.1109/TIT.1986.1057136](https://doi.org/10.1109%2FTIT.1986.1057136).[*[permanent dead link](https://en.wikipedia.org/wiki/Wikipedia:Link_rot)*] 1. **[^](#cite_ref-optimal_6-0)** Sulaiman Al-Bassam; Bella Bose (March 1990). "On Balanced Codes". *IEEE Transactions on Information Theory*. **36** (2): 406–408. [doi](/source/Doi_(identifier)):[10.1109/18.52490](https://doi.org/10.1109%2F18.52490). 1. **[^](#cite_ref-7)** [K. Schouhamer Immink](/source/Kees_Schouhamer_Immink) and J. Weber (2010). ["Very efficient balanced codes"](https://www.researchgate.net/publication/224110287). *IEEE Journal on Selected Areas in Communications*. **28** (2): 188–192. [doi](/source/Doi_(identifier)):[10.1109/jsac.2010.100207](https://doi.org/10.1109%2Fjsac.2010.100207). [S2CID](/source/S2CID_(identifier)) [8596702](https://api.semanticscholar.org/CorpusID:8596702). Retrieved 2018-02-12. 1. **[^](#cite_ref-8)** ["Demystifying MIPI C-PHY / DPHY Subsystem - Tradeoffs, Challenges, and Adoption"](https://www.design-reuse.com/articles/43954/demystifying-mipi-c-phy-dphy-subsystem.html) ([mirror](https://www.chipestimate.com/Demystifying-MIPI-C-PHY--DPHY-Subsystem-Tradeoffs-Challenges-and-Adoption-/Mixel/Technical-Article/2018/04/24)) ## External links - [Table of lower bounds on A ( n , d , w ) {\displaystyle A(n,d,w)}](http://www.win.tue.nl/~aeb/codes/Andw.html) maintained by [Andries Brouwer](/source/Andries_Brouwer) - [Table of upper bounds on A ( n , d , w ) {\displaystyle A(n,d,w)}](http://codes.se/bounds/) maintained by [Erik Agrell](https://en.wikipedia.org/w/index.php?title=Erik_Agrell&action=edit&redlink=1) --- Adapted from the Wikipedia article [Constant-weight code](https://en.wikipedia.org/wiki/Constant-weight_code) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Constant-weight_code?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.