Group code

In coding theory ( computer science ), a group code is a special coding that can be used for error detection and correction . A group (algebraic structure) is used for coding .

Coding

A group code is a block code , which means that all code words have the same length (in the following we denote the length of the code words ). ${\ displaystyle n}$

Any Abelian group is used as the alphabet for coding , usually the cyclic group of order two, as its two elements can be identified with bits 0 and 1. ${\ displaystyle (A, {\ mathord {+}})}$ ${\ displaystyle (\ {0.1 \}, {\ mathord {+}})}$

The source-coded words are the elements of the group . (All words with symbols from length ) ${\ displaystyle (A, {\ mathord {+}}) ^ {k}}$ ${\ displaystyle A}$ ${\ displaystyle k}$

An injective homomorphism is chosen to code the group . The image of is a subset of . ${\ displaystyle (A, {\ mathord {+}}) ^ {k}}$ ${\ displaystyle f \ colon (A, {\ mathord {+}}) ^ {k} \ to (A, {\ mathord {+}}) ^ {n}}$ ${\ displaystyle f}$ ${\ displaystyle (C, {\ mathord {+}})}$ ${\ displaystyle (A, {\ mathord {+}}) ^ {n}}$

${\ displaystyle C}$ is the group code. the associated coding function. ${\ displaystyle f}$

In contrast to “arbitrary” codings, each code word does not have to be specified (saved) separately, but it is sufficient to define a generating system of the group . The coding of the remaining elements can then be calculated using their representation as the sum of generating elements. ${\ displaystyle f}$ ${\ displaystyle f}$ ${\ displaystyle (A, {\ mathord {+}}) ^ {k}}$

Examples

example 1

group ${\ displaystyle (\ {0.1 \}, {\ mathord {+}})}$

Source coding: ${\ displaystyle (\ {0,1 \}, {\ mathord {+}}) ^ {3}}$

generating system: , , ${\ displaystyle e_ {1} = (1,0,0)}$ ${\ displaystyle e_ {2} = (0,1,0)}$ ${\ displaystyle e_ {3} = (0,0,1)}$

Coding: , , ${\ displaystyle f (e_ {1}) = (1,1,0,0,0)}$ ${\ displaystyle f (e_ {2}) = (0,0,1,1,0)}$ ${\ displaystyle f (e_ {3}) = (1,0,1,0,1)}$

Now be a word in source coding. To calculate the coding , proceed as follows: ${\ displaystyle c = (1,0,1)}$ ${\ displaystyle f (c)}$

One represents as the sum of generating elements: ${\ displaystyle c}$ ${\ displaystyle c = (1,0,1) = e_ {1} + e_ {3}}$

and then calculates the sum of the codes of the same ${\ displaystyle f (c) = f (e_ {1}) + f (e_ {3}) = (1,1,0,0,0) + (1,0,1,0,1) = (0 , 1,1,0,1)}$

Example 2

Group , the Klein group of four ${\ displaystyle (\ {0,1, x, x + 1 \}, {\ mathord {+}})}$

+	0	1	x	x + 1
0	0	1	x	x + 1
1	1	0	x + 1	x
x	x	x + 1	0	1
x + 1	x + 1	x	1	0

Source coding: ${\ displaystyle (\ {0,1, x, x + 1 \}, {\ mathord {+}}) ^ {2}}$

generating system: , , , ${\ displaystyle e_ {1} = (1,0)}$ ${\ displaystyle e_ {2} = (x, 0)}$ ${\ displaystyle e_ {3} = (0.1)}$ ${\ displaystyle e_ {4} = (0, x)}$

Coding: , , , ${\ displaystyle f (e_ {1}) = (1,0,0)}$ ${\ displaystyle f (e_ {2}) = (1,1,0)}$ ${\ displaystyle f (e_ {3}) = (x, 1,1)}$ ${\ displaystyle f (e_ {4}) = (0,0, x)}$

Now be a word in source coding. , , ${\ displaystyle c = (1, x + 1)}$ ${\ displaystyle c = e_ {1} + e_ {3} + e_ {4}}$ ${\ displaystyle f (c) = f (e_ {1}) + f (e_ {3}) + f (e_ {4}) = (1,0,0) + (x, 1,1) + (0 , 0, x) = (x + 1,1, x + 1)}$

properties

Group codes have the following properties:

The code words form a group
In the case of a binary group code, the distance distribution is the same for all code words and also the same as the weight distribution.
Each group code contains the " zero vector " as a valid code word.
The weight of a group code is defined as the smallest code word weight ( Hamming weight ) apart from that of the zero vector.

In the case of binary group codes, the Hamming distance corresponds to the weight of the code.