Tata Institute of Fundamental Research
Binary linear error correcting codes with sufficient symmetry achieve capacity on the erasure channel
STCS Student Seminar
Speaker:
Sreejata Kishor Bhattacharya
Organiser:
Eeshan Modak
Date:
Friday, 23 Sep 2022, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
Constructing error correcting codes that achieve Shannon capacity on a given memoryless channel and have efficient encoding and decoding algorithms has been a major line of recent research. In this talk, we shall discuss the error correcting capacity of codes on the binary erasure channel. We will show that sufficient symmetry alone implies a linear error correcting code achieves capacity on BEC. In particular, we shall prove the following results: (i) Consider a family of linear binary error correcting codes (parameterized by block length) approaching constant rate. Suppose the transitive group of each code is doubly symmetric and the distance satisfies log(distance)/log(block length)->1. Then this family achieves capacity on BEC. This implies that BCH codes achieve capacity on BEC. (ii) Binary Reed Muller codes achieve capacity on BEC. In this proof, we shall not use any special properties of Reed Muller codes other than the fact that their symmetry group contains GL_n(F_2) and that a family of Reed Muller codes approaching constant rate satisfies log(distance)/log(block length)->1/2.
| Speaker: | Sreejata Kishor Bhattacharya |
| Organiser: | Eeshan Modak |
| Date: | Friday, 23 Sep 2022, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
Constructing error correcting codes that achieve Shannon capacity on a given memoryless channel and have efficient encoding and decoding algorithms has been a major line of recent research. In this talk, we shall discuss the error correcting capacity of codes on the binary erasure channel. We will show that sufficient symmetry alone implies a linear error correcting code achieves capacity on BEC. In particular, we shall prove the following results: (i) Consider a family of linear binary error correcting codes (parameterized by block length) approaching constant rate. Suppose the transitive group of each code is doubly symmetric and the distance satisfies log(distance)/log(block length)->1. Then this family achieves capacity on BEC. This implies that BCH codes achieve capacity on BEC. (ii) Binary Reed Muller codes achieve capacity on BEC. In this proof, we shall not use any special properties of Reed Muller codes other than the fact that their symmetry group contains GL_n(F_2) and that a family of Reed Muller codes approaching constant rate satisfies log(distance)/log(block length)->1/2.