Algebraic Geometry Modeling In Information Theory

Edgar Martínez Moro

• Publisher: WSPC
• Year: 2012
• Print ISBN: 9789814335751
• eBook ISBN: 9789814483827
• Topic: Biological Sciences
• Subtopic: Science General
• Index: Biological Sciences

Algebraic & geometry methods have constituted a basic background and tool for people working on classic block coding theory and cryptography. Nowadays, new paradigms on coding theory and cryptography have arisen such as: Network coding, S-Boxes, APN Functions, Steganography and decoding by linear programming. Again understanding the underlying procedure and symmetry of these topics needs a whole bunch of non trivial knowledge of algebra and geometry that will be used to both, evaluate those methods and search for new codes and cryptographic applications. This book shows those methods in a self-contained form.

Contents:

• Sage: A Basic Overview for Coding Theory and Cryptography (D Joyner)
• Aspects of Random Network Coding (O Geil and C Thomsen)
• Steganography from a Coding Theory Point of View (C Munuera)
• An Introduction to LDPC Codes (I Márquez-Corbella & E Martínez-Moro)
• Numerical Semigroups and Codes (M Bras-Amorós)
• Codes, Arrangements and Matroids (R Jurrius & R Pellikaan)

Readership: Researchers in coding theory and cryptography.

Chapter 5

Codes, Arrangements and Matroids

Relinde Jurrius* and Ruud Pellikaan^†

Eindhoven University of Technology
Department of Mathematics and Computer Science, Coding and Crypto
P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands
*[email protected] ^†[email protected]

This chapter treats error-correcting codes and their weight enumerator as the center of several closely related topics such as arrangements of hyperplanes, graph theory, matroids, posets and geometric lattices and their characteristic, chromatic, Tutte, Möbius and coboundary polynomial, respectively. Their interrelations and many examples and counterexamples are given. It is concluded with a section with references to the literature for further reading and open questions.

AMS classification: 05B35, 05C31, 06A07, 14N20, 94B27, 94B70, 94C15

Contents

5.1 Introduction

5.2 Error-correcting codes

5.2.1 Codes and Hamming distance

5.2.2 Linear codes

5.2.3 Generator matrix

5.2.4 Parity check matrix

5.2.5 Inner product and dual codes

5.2.6 The Hamming and simplex codes

5.2.7 Singleton bound and MDS codes

5.3 Weight enumerators and error probability

5.3.1 Weight spectrum

5.3.2 The decoding problem

5.3.3 The q-ary symmetric channel

5.3.4 Error probability

5.4 Codes, projective systems and arrangements

5.5 The extended and generalized weight enumerator

5.5.1 Generalized weight enumerators

5.5.2 Extended weight enumerator

5.5.3 Puncturing and shortening of codes

5.5.4 Connections

5.5.5 MDS-codes

5.6 Matroids and codes

5.6.1 Matroids

5.6.2 Graphs, codes and matroids

5.6.3 The weight enumerator and the Tutte polynomial

5.6.4 Deletion and contraction of matroids

5.6.5 MacWilliams type property for duality

5.7 Posets and lattices

5.7.1 Posets, the Möbius function and lattices

5.7.2 Geometric lattices

5.7.3 Geometric lattices and matroids

5.8 The characteristic polynomial

5.8.1 The characteristic and coboundary polynomial

5.8.2 The Möbius polynomial and Whitney numbers

5.8.3 Minimal codewords and subcodes

5.8.4 The characteristic polynomial of an arrangement

5.8.5 The characteristic polynomial of a code

5.8.6 Examples and counte...

Table of contents

• Front Cover
• Half Title
• Series
• Title
• Copyright
• Preface
• Contents
• Sage: A Basic Overview for Coding Theory and Cryptography
• Aspects of Random Network Coding
• Steganography from a Coding Theory Point of View
• An Introduction to LDPC Codes
• Numerical Semigroups and Codes
• Codes, Arrangements and Matroids