Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17042 |
| _version_ | 1826194218226286592 |
|---|---|
| author | Bazzi, Louay Mohamad Jamil, 1974- |
| author2 | Sanjoy K. Mitter and Daniel A. Spielman. |
| author_facet | Sanjoy K. Mitter and Daniel A. Spielman. Bazzi, Louay Mohamad Jamil, 1974- |
| author_sort | Bazzi, Louay Mohamad Jamil, 1974- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. |
| first_indexed | 2024-09-23T09:52:43Z |
| format | Thesis |
| id | mit-1721.1/17042 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:52:43Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/170422019-04-10T16:45:55Z Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness Bazzi, Louay Mohamad Jamil, 1974- Sanjoy K. Mitter and Daniel A. Spielman. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. Includes bibliographical references (leaves 207-214). This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. We study the minimum distance of binary error correcting codes from the following perspectives: * The problem of deriving bounds on the minimum distance of a code given constraints on the computational complexity of its encoder. * The minimum distance of linear codes that are symmetric in the sense of being invariant under the action of a group on the bits of the codewords. * The derandomization capabilities of probability measures on the Hamming cube based on binary linear codes with good distance properties, and their variations. Highlights of our results include: * A general theorem that asserts that if the encoder uses linear time and sub-linear memory in the general binary branching program model, then the minimum distance of the code cannot grow linearly with the block length when the rate is nonvanishing. * New upper bounds on the minimum distance of various types of Turbo-like codes. * The first ensemble of asymptotically good Turbo like codes. We prove that depth-three serially concatenated Turbo codes can be asymptotically good. * The first ensemble of asymptotically good codes that are ideals in the group algebra of a group. We argue that, for infinitely many block lengths, a random ideal in the group algebra of the dihedral group is an asymptotically good rate half code with a high probability. * An explicit rate-half code whose codewords are in one-to-one correspondence with special hyperelliptic curves over a finite field of prime order where the number of zeros of a codeword corresponds to the number of rational points. (cont.) * A sharp O(k-1/2) upper bound on the probability that a random binary string generated according to a k-wise independent probability measure has any given weight. * An assertion saying that any sufficiently log-wise independent probability measure looks random to all polynomially small read-once DNF formulas. * An elaborate study of the problem of derandomizability of AC₀ by any sufficiently polylog-wise independent probability measure. * An elaborate study of the problem of approximability of high-degree parity functions on binary linear codes by low-degree polynomials with coefficients in fields of odd characteristics. by Louay M.J. Bazzi. Ph.D. 2005-05-19T15:46:05Z 2005-05-19T15:46:05Z 2003 2003 Thesis http://hdl.handle.net/1721.1/17042 54902058 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 214 leaves 953623 bytes 966561 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Bazzi, Louay Mohamad Jamil, 1974- Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness |
| title | Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness |
| title_full | Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness |
| title_fullStr | Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness |
| title_full_unstemmed | Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness |
| title_short | Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness |
| title_sort | minimum distance of error correcting codes versus encoding complexity symmetry and pseudorandomness |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/17042 |
| work_keys_str_mv | AT bazzilouaymohamadjamil1974 minimumdistanceoferrorcorrectingcodesversusencodingcomplexitysymmetryandpseudorandomness |