In
information theory
Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
, the bar product of two
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
s ''C''
2 ⊆ ''C''
1 is defined as
:
where (''a'' , ''b'') denotes the concatenation of ''a'' and ''b''. If the
code word
In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability, ...
s in ''C''
1 are of length ''n'', then the code words in ''C''
1 , ''C''
2 are of length 2''n''.
The bar product is an especially convenient way of expressing the
Reed–Muller RM (''d'', ''r'') code in terms of the Reed–Muller codes RM (''d'' − 1, ''r'') and RM (''d'' − 1, ''r'' − 1).
The bar product is also referred to as the , ''u'' , ''u''+''v'' , construction
or (''u'' , ''u'' + ''v'') construction.
Properties
Rank
The
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
of the bar product is the sum of the two ranks:
:
Proof
Let
be a basis for
and let
be a basis for
. Then the set
is a basis for the bar product
.
Hamming weight
The
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...
''w'' of the bar product is the lesser of (a) twice the weight of ''C''
1, and (b) the weight of ''C''
2:
:
Proof
For all
,
:
which has weight
. Equally
:
for all
and has weight
. So minimising over
we have
:
Now let
and
, not both zero. If
then:
:
If
then
:
so
:
See also
*
Reed–Muller code
Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in ...
References
{{DEFAULTSORT:Bar Product (Coding Theory)
Information theory
Coding theory