Digital Signal Processing

Digital Signal Processing: Applications to Communications and Algebraic Coding Theories discusses the design of computationally efficient digital signal processing algorithms over finite fields and the relation of these algorithms to algebraic error-correcting codes. The book provides chapters that cover such topics as signal processing techniques employed for modeling, synthesis, and analysis; systems of bilinear forms; efficient finite field algorithms; the design and study of long length cyclic convolutions and some preliminary results on their relation to linear codes; the study of the algebraic structure of the class of linear codes obtained from bilinear cyclic and aperiodic convolution algorithms over the finite field of interest; and the concept of a generalized hybrid Automatic- Repeat-Request (ARQ) scheme for adaptive error control in digital communication systems.

Engineers, mathematicians, and computer scientists will find the text invaluable.

Preface

Acknowledgments

1 Overview and Perspective

1.1 Introduction

1.2 Breadth and Depth

1.3 References

2 Systems of Bilinear Forms

2.1 The Program Model

2.2 Multiplicative Complexity

2.3 Dual of a Bilinear Form

2.4 A Particular Bilinear Form

2.5 References

3 Efficient Finite Field Algorithms

3.1 Cyclic Convolution

3.1.1 Algorithm Development

3.1.2 Algorithm Steps

3.1.3 Length p — 1 Algorithms Over a Field of Constants GF(p)

3.1.4 Length N Algorithms Over a Field of Constants GF(p) When (N,p) = 1

3.1.5 Multiplicative Complexity

3.1.6 Additive Complexity

3.2 Aperiodic Convolution

3.2.1 The Toom-Cook Algorithm

3.2.2 Embedding of Aperiodic Convolution: Higher-Dimensional Approaches

3.2.3 Aperiodic Convolution with Wraparound

3.3 References

3.4 Appendix A

3.5 Appendix B

3.6 Appendix C

4 Multidimensional Methods

4.1 Long Length Cyclic Convolution

4.1.1 Mutual Prime Factor Versus Direct Designs

4.1.2 Some Specific Results Pertinent to Long Length Design

4.2 Multiplicative Complexity

4.3 A Distance Bound

4.4 References

4.5 Appendix A

4.6 Appendix B

5 A New Class of Linear Codes

5.1 Multidimensional Algorithms and Codes

5.2 CRT Algorithms and Codes

5.2.1 CRT-Based Convolution Algorithms over GF(2) and the Related Codes

5.2.2 CRT-Based Convolution Algorithms over GF(3) and the Related Codes

5.2.3 A Shift Register-Based Encoding Procedure

5.3 Error Detection

5.3.1 Burst Error Detection Capability

5.4 Error Correction

5.4.1 Experimental Results

5.4.2 Code Family Encoding/Decoding Relationships

5.5 Discussion

5.6 References

5.7 Appendix A

5.8 Appendix B

6 A New Error Control Scheme

6.1 ARQ Schemes

6.2 Hybrid ARQ Schemes

6.3 Generalized Type-II Hybrid ARQ Schemes

6.4 A Brief Review of the KM Codes

6.5 A GH-ARQ Scheme Based on KM Codes

6.6 GH-ARQ Error Detection

6.7 Reliability and Throughput

6.8 Soft-Decision Decoding

6.8.1 Background

6.8.2 System Performance

6.8.3 Performance Comparisons

6.8.4 Soft-Decision GH-ARQ Code Alternatives

6.9 References

6.10 Appendix A

6.11 Appendix B

6.12 Appendix C