Applied Modern Algebra

Title
Preface
Contents
1. Sets and Functions
1.1. Sets
1.2. The Indexing of Sets
1.3. Sets Derived from Other Sets
1.4. The Order of a Set
1.5. Functions
1.6. Exercises
1.7. More Notation
1.8. One-to-One and Onto
1.9. Composition and Inversion of Functions
1.10. Exercises
1.11. Finite-State Machines
1.12. Construction of Machines
1.13. Exercises
1.14. Union, Intersection, and Inclusion
1.15. Complementation
1.16. Venn Diagrams
1.17. More Algebra of Subsets
1.18. The Principle of Duality
1.19. Boolean Algebras; Summary of Basic Laws
1.20. Mathematical Induction
1.21. The Characteristic Function of a Subset of a Set
1.22. Exercises
2. Relations and Graphs
2.1. Relations
2.2. A Matrix Model of Finite Relations
2.3. The Composition of Relations
2.4. Matrix Equivalent of Composition; Digraphs
2.5. Relations on a Set A
2.6. Functions as Relations
2.7. Exercises
2.8. Partial Orderings and Posets
2.9. Special Elements of Posets
2.10. Direct Products of Posets
2.11. Exercises
2.12. Equivalence Relations and Partitions
2.13. Intersection and Union of Equivalence Relations
2.14. Intersection and Union of Partitions
2.15. Exercises
2.16. Identification of Equivalent States
2.17. Minimal-State Machines
2.18. Distinguishing Sequences for States
2.19. Exercises
2.20. Undirected Graphs
2.21. Trees
2.22. Exercises
2.23. Spanning Trees
2.24. Fundamental Circuits and Cut-Sets
2.25. Applications and Famous Problems
2.26. Exercises
3. Rings and Boolean Algebras
3.1. Algebras
3.2. Rings
3.3. Congruences
3.4. The Ring of Integers Modulo p
3.5. Binary Arithmetic Modulo 2`n
3.6. Exercises
3.7. Boolean Rings and Boolean Algebras
3.8. Independent Postulates for a Boolean Algebra
3.9. Exercises
3.10. The Algebraic Description of Logic Circuits
3.11. Switching Functions and Their Basic Properties
3.12. Exercises
3.13. Disjunctive and Conjunctive Normal Forms
3.14. The Exclusive-OR and the Ring Normal Form of f
3.15. Inequalities in Switching Algebra
3.16. Exercises
3.17. Prime Implicants and Minimal Sums of Products
3.18. Reusch’s Method for Finding All Prime Implicants
3.19. The Minimal Sums of a Function
3.20. Reusch’s Method for Finding All Minimal Sums
3.21. Exercises
3.22. Conclusion
4. Semigroups and Groups
4.1. Definitions
4.2. Zeros and Identities
4.3. Cyclic Semigroups and Cyclic Groups
4.4. Subsemigroups and Subgroups
4.5. Exercises
4.6. Congruence Relations on Semigroups
4.7. Morphisms
4.8. The Semigroup of a Machine
4.9. The Machine of a Semigroup
4.10. Exercises
4.11. Equations in Semigroups
4.12. Lagrange’s Theorem
4.13. Direct Products
4.14. Normal Subgroups
4.15. Exercises
4.16. Structure of Cyclic Groups
4.17. Permutation Groups
4.18. Dihedral Groups
4.19. Additive Abelian Groups
4.20. Exercises
5. Applications of Group Theory
5.1. The Binary Symmetric Channel
5.2. Block Codes
5.3. Weight and Distance
5.4. Generator and Parity-Check Matrices
5.5. Exercises
5.6. Group Codes
5.7. Coset Decoding
5.8. Hamming Codes
5.9. Extended Hamming Codes
5.10. Exercises
5.11. Fast Adders: Winograd’s Theory
5.12. Fast Adders: Procedures
5.13. Exercises
5.14. Pólya Enumeration Theory
5.15. Exercises
5.16. An Extension of Pólya Enumeration Theory
5.17. Equivalence Classes of Switching Functions
5.18. Exercises
6. Lattices
6.1. Definition of a Lattice
6.2. A Basic Theorem
6.3. The Operations “Cup” and “Cap”
6.4. Another Description of a Lattice
6.5. The Modular and Distributive Laws
6.6. Complements in Lattices
6.7. Exercises
6.8. Free Distributive Lattices
6.9. Compatibility Relations and Covers
6.10. Atomic Lattices and Boolean Algebras
6.11. Exercises
6.12. Closed Partitions in a Finite-State Machine
6.13. Series and Parallel Decomposition of Machines
6.14. Exercises
7. Linear Algebra and Field Theory
7.1. Matrices
7.2. Elementary Row Operations
7.3. The Inverse of a Matrix
7.4. Exercises
7.5. Vector Spaces
7.6. Linear Independence and Dimension
7.7. Exercises
7.8. Linear Transformations
7.9. Matrices of Linear Transformations
7.10. Rank
7.11. Exercises
7.12. Determinants
7.13. Similarity
7.14. Exercises
7.15. Ideals and Homomorphisms in Rings
7.16. Polynomial Rings
7.17. Rational Canonical Form
7.18. Exercises
7.19. Field Extensions
7.20. Finite Fields
7.21. Computation in Finite Fields
7.22. Exercises
7.23. Automorphisms of Finite Fields
7.24. Number of Irreducibles
7.25. Exercises
8. Linear Machines
8.1. Definition
8.2. Shift Registers
8.3. Characterizing Matrices
8.4. Exercises
8.5. The Distinguishing Matrix
8.6. Minimization of Linear Machines
8.7. Exercises
8.8. Rational Transfer Functions
8.9. Impulse Response
8.10. Exercises
8.11. Autonomous Linear Machines
8.12. Cycle Structure of Feedback Shift Registers
8.13. Recursive Equations
8.14. Exercises
8.15. Null Sequences
8.16. Circulating Shift Registers
8.17. Section 5.17 Revisited
8.18. Exercises
9. Algebraic Coding Theory
9.1. Codes over GF(q)
9.2. Exercises
9.3. Cyclic Codes
9.4. BCH Codes
9.5. Reed-Solomon Codes; Burst Error Correction
9.6. Encoding Cyclic Codes
9.7. Exercises
9.8. BCH Decoding as an FSR Problem
9.9. Shortest FSR with Given Output
9.10. Algorithmic BCH Decoding
9.11. Exercises
9.12. Binary BCH Decoding
9.13. The Cyclic Redundancy Check
9.14. Fire Codes
9.15. Some Coding Tricks
9.16. How Good Can a Code Be?
9.17. Exercises
Bibliography
Index