多伦多大学纠错编码lecture02

Lecture of September22nd,20151Codes and Code RateWe now start our formal study of coding theory.If X is anyfinite set,then|X|denotes the cardinality of X,i.e.,the number of distinct elements contained in X.An alphabet is a nonempty set of symbols.If A is an alphabet,then A n=A×A×···×An times ={(a1,a2,...,a n):a1,a2,...,a n∈A}denotes the set of n-tuples over A.Definition1.A code C of block length n over an alphabet A of size q>1is a nonempty subset of A n.The elements of C are referred to as codewords,and C itself is referred to as a q-ary code.Note that Definition1is very general,and includes linear codes(i.e.,codes,like the binary Hamming codes,defined by linear systems of equations)as well as many nonlinear codes.While we primarily study linear codes in this course, we will,for the moment,consider general codes.Definition2.When q isfinite,the rate of a q-ary code C of block length n is R=1n log q|C|,measured in q-arysymbols per channel use.Note that0≤R≤1.Some authors prefer to always measure rate in units of bits per channel use,irrespectivelyof the alphabet size q,defining R=1n log2|C|.In this case,0≤R≤log2q.While the two notions of ratecoincide when q=2,for q>2the particular notion of rate being used must be made clear.As an example,the set C={000,111},taken as a code over the binary alphabet{0,1},has rate1/3.As computed earlier,the binary (n,k)=(2m−1,2m−1−m)Hamming code has rate R=k/n=1−m/(2m−1).2Hamming DistanceRecall that a metric(or distance function)defined on a set X is a function d:X×X→R that satisfies for all x,y,z∈X1.non-negativity:d(x,y)≥0,with d(x,y)=0if and only if x=y;2.symmetry:d(x,y)=d(y,x);3.the triangle inequality:d(x,y)≤d(x,z)+d(z,y).In the context of error correction and erasure correction,Hamming distance plays a pivotal role.Definition3.The Hamming distance d(x,y)between two n-tuples x=(x1,...,x n)and y=(y1,...,y n)in A n isd(x,y)=|{i:x i=y i,i∈{1,...,n}}|,equal to the number of coordinate positions in which x and y are different.It is straightforward to prove the following theorem.Lecture Notes,Fall2015c F.R.Kschischang1Theorem1.Hamming distance is a metric on A n.Proof.Left as an exercise.If x is transmitted and y is received,then d(x,y)is equal to the number of errors that occurred in transmission. In a sense,Hamming distance provides a measure of dissimilarity between n-tuples:the greater is the Hamming distance between x and y,the greater is their dissimilarity.In many channels(e.g.,the binary symmetric channel with crossover probability p<1/2),the greater is the Hamming distance between x and y,the less likely is y to be received when x is transmitted.An important parameter of a code is the minimum Hamming distance between any two of its codewords.Definition4.The minimum Hamming distance of a code C with|C|>1isd min(C)=min{d(x,y):x,y∈C,x=y}.By convention,a code C having just one codeword has d min(C)=∞.For example,d min({000,111})=3,d min({000,011,101,110})=2.3Error-Correcting Capability of a CodeSuppose we are given a channel whose input alphabet X and output alphabet Y are the same.In this case,there is a well-defined notion of Hamming distance between channel inputs and channel outputs,and the concept of a minimum distance decoder is well defined.Definition5.A minimum distance decoder for a code C is a function D:Y n→C such thatd(D(y),y)≤d(x,y)for all x∈C.More plainly,given any y∈Y n,a minimum distance decoder returns a valid codeword nearest,in the sense of Hamming distance,to y.For x∈C,the inverse image of x under D,i.e.,the setD−1(x)={y:D(y)=x}⊆Y nis the decoding region associated with codeword x.It is clear that Y n can be written as the disjoint union of the decoding regions associated with the codewords,i.e.,1Y n=D−1(x),x∈Cas illustrated in Figure1.A minimum distance decoder is complete,i.e.,it will return a codeword for every possible y.Definition6.A Hamming ball of radius t and center x is the setB x(t)={y∈Y n:d(x,y)≤t}.1The symbol is used to denote a union of disjoint sets.Lecture Notes,Fall2015c F.R.Kschischang2Figure1:A schematic view of the space of possible received words,partitioned into the decoding regions associated with the codewords of a code.The shaded region is D−1(x),the decoding region associated with codeword x.Definition7.Given t≥0,let C be a code such that B x(t)∩B x (t)=∅for all distinct codewords x and x of C.A bounded distance decoder for C with decoding radius t is a functionD:Y n→C∪{f}such thatD(y)=x,if y∈B x(t);f,otherwise.Note that the bounded distance decoder D with decoding radius t is well-defined(exists)if and only if the radius-t Hamming balls centered at the codewords are disjoint.When D(y)=f we say that a decoding failure is declared. Since decoding failures are a possibility,bounded distance decoders are,in general,said to be incomplete.A schematic view of the decoding regions for a bounded distance decoder is given in Figure2.Figure2:A schematic view of the space of possible received words,partitioned into the decoding regions associated with a bounded distance decoder.The shaded region corresponds to received words for which a decoding failure is declared.An example application for a bounded distance decoder arises by setting the decoding radius t to zero.In this case B x(0)={x},and the decoder declares a decoding failure whenever it receives a non-codeword.Such a decoder is called an error-detecting decoder.Note that a bounded distance decoder with decoding radius t is t-error-correcting,i.e.,every pattern of t or fewer errors is corrected.Theorem2.A bounded distance decoder with decoding radius t exists for C if and only if d min(C)>2t.Proof.Suppose d min(C)>2t.We must show that B x(t)and B x (t)are disjoint for distinct codewords x,x ∈C,i.e., a bounded distance decoder with decoding radius t exists.Accordingly,take y∈B x(t).We have2t<d min(C)≤d(x,x ).By the triangle inequality,2t<d(x,x )≤d(x,y)+d(y,x ).Since d(x,y)≤t,this forces d(y,x )>t,i.e.,y∈B x (t).Lecture Notes,Fall2015c F.R.Kschischang3Conversely,suppose a bounded distance decoder with decoding radius t exists,so that B x(t)and B x (t)are disjoint for every pair of distinct codewords x,x ∈C.We must show that d(x,x )>2t.Suppose,to the contrary,that d(x,x )≤2t for some pair of distinct codewords.Then it is possible to construct a y such that d(x,y)≤t and d(x ,y)≤t,which would imply that B x(t)∩B x (t)is not empty,acontradiction.We see that a bounded distance decoder for C with decoding radius t exists if and only ift≤t∗=d min(C)−1.We call t∗the unique decoding radius of C.4Erasure-Correcting Capability of a CodeLet X by the input alphabet for an erasure channel and let Y=X∪{φ}be the output alphabet(whereφ∈X is the erasure symbol).An erasure channel never commits errors;it can only erase some subset of the transmitted symbols,i.e.,replace the symbols in the chosen subset with the erasure symbol.Let C be a code of block length n for the erasure channel,and define a decoder D:Y n→C∪{f}whereD(y)=x,if y agrees with exactly one x∈C on all of its un-erased positions;f,otherwise.Such a decoder is said to be e-erasure-correcting if D returns a codeword whenever it is given a codeword x corrupted by any pattern of e or fewer erasures.Theorem3.An e-erasure-correcting decoder for C exists if and only if d min(C)>e.Proof.Starting from distinct codewords x and x ,we can arrive at the same channel output y only by erasing a set containing the positions in which x and x differ;this requires at least d min(C)erasures.Thus if fewer than d min(C) erasures occur when x is sent,only x will agree with y on all of its un-erased positions and D will produce x. Conversely,let x and x be distinct codewords differing in d min(C)positions.By erasing the d min positions in which x and x disagree,it is possible to produce a channel output that agrees with both x and x on its un-erased positions. No decoder can unambiguously recover from this occurrence;thus if d min(C)≤e an e-erasure-correcting decoder for C does notexist.If the channel produces both errors and erasures,the following theorem characterizes the combined error-and-erasure correcting capability of a code C.Theorem4.A decoder for C exists that can simultaneously correct all patters of up to t errors and all patterns of up to e erasures if d min(C)>2t+e.Conversely,if d min(C)≤2t+e,it is possible to produce a channel output consistent with the transmission of more than one codeword corrupted by≤t errors and≤e erasures.This theorem implies that there is an“exchange rate”between errors and erasures;erasures“cost”half as much as errors.Lecture Notes,Fall2015c F.R.Kschischang4DiscussionIt is clear that the minimum distance d min(C)of a code C is a critical parameter,along with the code’s cardinality |C|and block length n.Let usfix the code alphabet A,let C be a code over A with block length n,let M=|C|,and let d=d min(C).Then C is called an(n,M,d)code2.One central problem of classical coding theory is to understand for which combinations of(n,M,d)codes over A exist.Suppose an(n,M,d)code C exists.Then so does an(n ,M,d)code C with n ≥n:simply append sufficiently many fixed dummy symbols to each codeword of C to create the codewords of C .Similarly,an(n,M ,d )code C with M ≤M and d ≥d also exists(provided M >0):simply expurgate sufficiently many codewords from C to obtain C ;this cannot reduce(and may increase)the minimum distance between codewords.Similarly,an(n,M,d )code C with d ≤d also exists(provided d >0):simply replace thefirst sufficiently many symbols of every codeword of C with afixed dummy symbol.It therefore becomes interesting to ask the following design questions:1.Given positive integers n and d,design a code C of block length n over A having d min(C)≥d,with|C|aslarge as possible.2.Given positive integers n and M,design a code C of block length n over A having|C|≥M,with d min(C)aslarge as possible.3.Given positive integers d and M,design a code C over A having d min(C)≥d,|C|≥M,and block length n assmall as possible.These variations of the code design problem are all attempts to understand the outer limits on which combinations of(n,M,d)are possible to achieve over the alphabet A.2Caution:this notation conflicts with that used in linear coding theory,where an(n,k,d)code over afield of q elements has M=q k codewords.Which usage is intended must be determined from the context.Lecture Notes,Fall2015c F.R.Kschischang5。