Binary Linear Codes
2-1 Introduction
An important class of error-control codes which is called linear block codes is described. Almost all the block codes used in error-control system are linear codes, and most of the known good codes belong to this class. This class of codes is defined by imposing a strong structural property. This chapter, also, introduces a description of cyclic codes, describes how to generate them, and presents the BCH codes as an example to the cyclic codes.
2-2 Definition
A linear block code or LBC (n , k) is a collection of vectors(n- tuples), called code words or code vectors, all are of the same length n, of which k bits are information bits(the number of parity bits is therefore n-k). it has the following properties; the sum of any two code words is also a codeword, it contains the zero vector, i.e , the all-zero n- tuple, which means that it forms a k-dimensional subspace of all n-tuples. the code rate R (or the efficiency of a code) is the number of information bits entering the encoder per transmitted channel bit. i.e , R = k/n.
The symbols of binary codes are drawn from the finite field GF(2) in which the alphabet has two symbols, 0 and 1 , and the addition and multiplication can be defined as follows:-
0+0=0 0.0=0
0+1=1 0.1=0
1+0=1 1.0=0
1+1=0 1.1=1
These are called modulo-2 addition and multiplication.
2-3 The distance concepts
The (Hamming) weight of an n- tuple v, w(v) is defined as the number of nonzero components of v; i.e, if v=(101011001), w(v)=5.
The (Hamming) distance between u and v , where u and v are two n-tuples, d(u,v), is defined as the number of components in which they differ; i.e, if:
u= (100101101
v= (110010101)
then d(u,v)= 4.
The relationship between the weight and distance is: d(u,v) = w(u+v) that is, the distance between u and v is just equal to the weight of their vector sum. Consider the two n-tuples given above,
u+v = (010111000)
w(u+v) = 4
which is just d(u,v) = 4.
The weight distribution of a code is the number of vectors of any weight in the code. This is often described by the list of numbers Ai where Ai is the number of vectors of weight I in the code. A0 is always 1.
The minimum (Hamming) weight of a code is the minimum result obtained by measuring the Hamming weight of all the code words, excluding the codeword consisting only of 0’s.
The minimum (Hamming)distance d of a code is minimum result obtained by measuring the distance between all possible pairs of the code words.
An important observation is that in a linear code, the minimum Hamming weight equals the minimum Hamming distance. This is because, if u and v are two code vector of a LBC, then (u+v) must also be a code vector, by definition of linear code, and since the distance between any two code vector is equal to the weight of a third code vector, thus the minimum distance of a linear code is equal to minimum weight of its nonzero code vector.
The minimum weight or minimum distance is the third parameter of a code (besides n and k) and it is very important since it determines the error-detecting/correcting capability of a code.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .