Block code: Difference between revisions

Revision as of 05:00, 22 November 2022

Revision as of 05:00, 22 November 2022

Line 24:

=== The alphabet Σ ===

The data stream to be encoded is modeled as a [[string (computer science)|string]] over some '''alphabet''' <math>\Sigma</math>. The size <math>|\Sigma|</math> of the alphabet is often written as <math>q</math>. If <math>q=2</math>, then the block code is called a ''binary'' block code. In many applications it is useful to consider <math>q</math> to be a [[prime power]], and to identify <math>\Sigma</math> with the [[finite field]] <math>\mathbb F_q</math>.

=== The message length ''k'' ===

Messages are elements <math>m</math> of <math>\Sigma^k</math>, that is, strings of length <math>k</math>.

Hence the number <math>k</math> is called the '''message length''' or '''dimension''' of a block code.

=== The block length ''n'' ===

The '''block length''' <math>n</math> of a block code is the number of symbols in a block. Hence, the elements <math>c</math> of <math>\Sigma^n</math> are strings of length <math>n</math> and correspond to blocks that may be received by the receiver. Hence they are also called received words.

If <math>c=C(m)</math> for some message <math>m</math>, then <math>c</math> is called the codeword of <math>m</math>.

=== The rate ''R'' ===

The '''rate''' of a block code is defined as the ratio between its message length and its block length:

:<math>R=k/n</math>.

A large rate means that the amount of actual message per transmitted block is high. In this sense, the rate measures the transmission speed and the quantity <math>1-R</math> measures the overhead that occurs due to the encoding with the block code.

It is a simple [[information theory|information theoretical]] fact that the rate cannot exceed <math>1</math> since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code <math>C</math> is an injective map.

=== {{anchor|Minimum distance}}The distance ''d'' ===