logo资料库

【国外通信教程】Solution Manual.Error Control Coding 2nd·Lin Shu.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：1.04M 资料格式：pdf 举报 版权申诉
第1页 / 共126页
第2页 / 共126页
第3页 / 共126页
第4页 / 共126页
第5页 / 共126页
第6页 / 共126页
第7页 / 共126页
第8页 / 共126页
资料共126页，剩余部分请下载后查看
    Chapter 2 2.3 Since m is not a prime, it can be factored as the product of two integers a and b, m = a · b with 1 < a, b < m. It is clear that both a and b are in the set {1, 2,··· , m − 1}. It follows from the definition of modulo-m multiplication that a b = 0. Since 0 is not an element in the set {1, 2,··· , m−1}, the set is not closed under the modulo-m multiplication and hence can not be a group. 2.5 It follows from Problem 2.3 that, if m is not a prime, the set {1, 2,··· , m − 1} can not be a group under the modulo-m multiplication. Consequently, the set {0, 1, 2,··· , m − 1} can not be a field under the modulo-m addition and multiplication. 2.7 First we note that the set of sums of unit element contains the zero element 0. For any 1 ≤ 1 + 1 = 1 = 0. i=1 i=1 i=1 Hence every sum has an inverse with respect to the addition operation of the field GF(q). Since the sums are elements in GF(q), they must satisfy the associative and commutative laws with respect to the addition operation of GF(q). Therefore, the sums form a commutative group under the addition of GF(q). Next we note that the sums contain the unit element 1 of GF(q). For each nonzero sum 1 with 1 ≤ < λ, we want to show it has a multiplicative inverse with respect to the multipli- cation operation of GF(q). Since λ is prime, and λ are relatively prime and there exist two i=1 1 < λ, λ− λ
    integers a and b such that a · + b · λ = 1, where a and λ are also relatively prime. Dividing a by λ, we obtain a = kλ + r with 0 ≤ r < λ. Since a and λ are relatively prime, r = 0. Hence Combining (1) and (2), we have 1 ≤ r < λ · r = −(b + k) · λ + 1 (1) (2) Consider r 1 · i=1 i=1 1 = ·r λ i=1 −(b+k)·λ −(b+k) i=1 1 = +1 = ( 1)( 1) + 1 i=1 i=1 = 0 + 1 = 1. Hence, every nonzero sum has an inverse with respect to the multiplication operation of GF(q). Since the nonzero sums are elements of GF(q), they obey the associative and commutative laws with respect to the multiplication of GF(q). Also the sums satisfy the distributive law. As a result, the sums form a field, a subfield of GF(q). 2.8 Consider the finite field GF(q). Let n be the maximum order of the nonzero elements of GF(q) and let α be an element of order n. It follows from Theorem 2.9 that n divides q − 1, i.e. q − 1 = k · n. Thus n ≤ q − 1. Let β be any other nonzero element in GF(q) and let e be the order of β. 2
    Suppose that e does not divide n. Let (n, e) be the greatest common factor of n and e. Then e/(n, e) and n are relatively prime. Consider the element β(n,e) This element has order e/(n, e). The element αβ(n,e) has order ne/(n, e) which is greater than n. This contradicts the fact that n is the maximum order of nonzero elements in GF(q). Hence e must divide n. Therefore, the order of each nonzero element of GF(q) is a factor of n. This implies that each nonzero element of GF(q) is a root of the polynomial X n − 1. Consequently, q − 1 ≤ n. Since n ≤ q − 1 (by Theorem 2.9), we must have n = q − 1. Thus the maximum order of nonzero elements in GF(q) is q-1. The elements of order q − 1 are then primitive elements. 2.11 (a) Suppose that f (X) is irreducible but its reciprocal f∗(X) is not. Then f∗(X) = a(X) · b(X) where the degrees of a(X) and b(X) are nonzero. Let k and m be the degrees of a(X) and b(X) respectivly. Clearly, k + m = n. Since the reciprocal of f∗(X) is f (X), f (X) = X nf∗( 1 X ) = X ka( 1 X ) · X mb( 1 X ). This says that f (X) is not irreducible and is a contradiction to the hypothesis. Hence f∗(X) must be irreducible. Similarly, we can prove that if f∗(X) is irreducible, f (X) is also irreducible. Consequently, f∗(X) is irreducible if and only if f (X) is irreducible. 3
    (b) Suppose that f (X) is primitive but f∗(X) is not. Then there exists a positive integer k less than 2n − 1 such that f∗(X) divides X k + 1. Let X k + 1 = f∗(X)q(X). Taking the reciprocals of both sides of the above equality, we have 1 X X k + 1 = X kf∗( = X nf∗( = f (X) · X k−nq( 1 X 1 X 1 X ). ) )q( ) · X k−nq( 1 X ) This implies that f (X) divides X k + 1 with k < 2n − 1. This is a contradiction to the hypothesis that f (X) is primitive. Hencef∗(X) must be also primitive. Similarly, if f∗(X) is primitive, f (X) must also be primitive. Consequently f∗(X) is primitive if and only if f (X) is primitive. 2.15 We only need to show that β, β2,··· , β2e−1 are distinct. Suppose that for 0 ≤ i, j < e and i < j. Then, β2i = β2j (β2j−i−1)2i = 1. Since the order β is a factor of 2m − 1, it must be odd. For (β2j−i−1)2i = 1, we must have β2j−i−1 = 1. Since both i and j are less than e, j − i < e. This is contradiction to the fact that the e is the smallest nonnegative integer such that β2e−1 = 1. 4
    Hence β2i = β2j for 0 ≤ i, j < e. 2.16 Let n be the order of β2i. Then Hence (β2i)n = 1 (βn )2i = 1. (1) Since the order n of β is odd, n and 2i are relatively prime. From(1), we see that n divides n and Now consider n = kn. (β2i)n = (βn)2i = 1 This implies that n (the order of β2i) divides n. Hence From (2) and (3), we conclude that n = n n = n. (2) (3) 2.20 Note that c· v = c· (0 + v) = c· 0 + c· v. Adding −(c· v) to both sides of the above equality, we have c · v + [−(c · v)] = c · 0 + c · v + [−(c · v)] 0 = c · 0 + 0. Since 0 is the additive identity of the vector space, we then have c · 0 = 0. 2.21 Note that 0 · v = 0. Then for any c in F , (−c + c) · v = 0 5
    (−c) · v + c · v = 0. Hence (−c) · v is the additive inverse of c · v, i.e. Since c · 0 = 0 (problem 2.20), −(c · v) = (−c) · v c · (−v + v) = 0 c · (−v) + c · v = 0. Hence c · (−v) is the additive inverse of c · v, i.e. −(c · v) = c · (−v) From (1) and (2), we obtain −(c · v) = (−c) · v = c · (−v) (1) (2) 2.22 By Theorem 2.22, S is a subspace if (i) for any u and v in S, u + v is in S and (ii) for any c in F and u in S, c · u is in S. The first condition is now given, we only have to show that the second condition is implied by the first condition for F = GF (2). Let u be any element in S. It follows from the given condition that u + u = 0 is also in S. Let c be an element in GF(2). Then, for any u in S,  0 f or u f or c · u = c = 0 c = 1 Clearly c · u is also in S. Hence S is a subspace. 2.24 If the elements of GF(2m) are represented by m-tuples over GF(2), the proof that GF(2m) is 6
    a vector space over GF(2) is then straight-forward. 2.27 Let u and v be any two elements in S1 ∩ S2. It is clear the u and v are elements in S1, and u and v are elements in S2. Since S1 and S2 are subspaces, and u + v ∈ S1 u + v ∈ S2. Hence,u + v is in S1 ∩ S2. Now let x be any vector in S1 ∩ S2. Then x ∈ S1, and x ∈ S2. Again, since S1 and S2 are subspaces, for any c in the field F , c · x is in S1 and also in S2. Hence c · v is in the intersection, S1 ∩ S2. It follows from Theorem 2.22 that S1 ∩ S2 is a subspace. 7
    Chapter 3 3.1 The generator and parity-check matrices are: 0 1 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 G =   H =  1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 1 0 1  1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 From the parity-check matrix we see that each column contains odd number of ones, and no two columns are alike. Thus no two columns sum to zero and any three columns sum to a 4- tuple with odd number of ones. However, the first, the second, the third and the sixth columns sum to zero. Therefore, the minimum distance of the code is 4. 3.4 (a) The matrix H1 is an (n− k +1)× (n + 1) matrix. First we note that the n− k rows of H are linearly independent. It is clear that the first (n− k) rows of H1 are also linearly independent. The last row of H1 has a 1 at its first position but other rows of H1 have a 0 at their first position. Any linear combination including the last row of H1 will never yield a zero vector. Thus all the rows of H1 are linearly independent. Hence the row space of H1 has dimension n − k + 1. The dimension of its null space, C1, is then equal to dim(C1) = (n + 1) − (n − k + 1) = k Hence C1 is an (n + 1, k) linear code. (b) Note that the last row of H1 is an all-one vector. The inner product of a vector with odd weight and the all-one vector is 1. Hence, for any odd weight vector v, v · HT 1 = 0 and v cannot be a code word in C1. Therefore, C1 consists of only even-weight code words. (c) Let v be a code word in C. Then v · HT = 0. Extend v by adding a digit v∞ to its left. 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料