Block code

There is a vast number of examples for block codes, many of which have a wide range of practical applications.

Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.

When a sender wants to transmit a possibly very long data stream using a block code, the sender breaks the stream up into pieces of some fixed size.

The sender then transmits all blocks to the receiver, who can in turn use some decoding mechanism to (hopefully) recover the original messages from the possibly corrupted received blocks.

The performance and success of the overall transmission depends on the parameters of the channel and the block code.

Formally, a block code is an injective mapping Here,

The data stream to be encoded is modeled as a string over some alphabet

is called the message length or dimension of a block code.

In this sense, the rate measures the transmission speed and the quantity

measures the overhead that occurs due to the encoding with the block code.

It is a simple information theoretical fact that the rate cannot exceed

Besides, the distance equals the minimum weight for linear block codes because:[citation needed] A larger distance allows for more error correction and detection.

For example, if we only consider errors that may change symbols of the sent codeword but never erase or add them, then the number of errors is the number of positions in which the sent codeword and the received word differ.

, but sometimes the precise distance is not known, non-trivial to prove or state, or not needed.

In the shorthand notation above, this means that the Hamming(7,4) code is a

, a set of lower and upper bounds of block codes are known.

The Singleton bound is that the sum of the rate and the relative distance of a block code cannot be much larger than 1: In other words, every block code satisfies the inequality

be the maximum number of codewords in a Hamming ball of radius e for any code

Block codes are tied to the sphere packing problem which has received some attention over the years.

Take a bunch of pennies flat on the table and push them together.

The result is a hexagon pattern like a bee's nest.

But block codes rely on more dimensions which cannot easily be visualized.

The powerful Golay code used in deep space communications uses 24 dimensions.

If used as a binary code (which it usually is), the dimensions refer to the length of the codeword as defined above.

The theory of coding uses the N-dimensional sphere model.

For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners.

As the dimensions get larger, the percentage of empty space grows smaller.

Another property is the number of neighbors a single codeword may have.

The result is that the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well.

It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.