Constant-weight code: Difference between revisions

Revision as of 12:19, 16 September 2010

Revision as of 23:30, 7 February 2011

Line 1:

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

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.

Line 21 ⟶ 20:

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

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

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

|-

|}

== References ==