Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: Algorithmica

Search In Journal Title:

Abbravation: Algorithmica

Search In Journal Abbravation:

Publisher

Springer-Verlag

Search In Publisher:

DOI

10.1006/jsre.1999.5590

Search In DOI:

ISSN

1432-0541

Search In ISSN:
Search In Title Of Papers:

Random Matrices and Codes for the Erasure Channel

Authors: Chris Studholme Ian F Blake
Publish Date: 2008/04/24
Volume: 56, Issue: 4, Pages: 605-620
PDF Link

Abstract

The design of erasure correcting codes and their decoding algorithms is now at the point where capacity achieving codes are available with decoding algorithms that have complexity that is linear in the number of information symbols One aspect of these codes is that the overhead number of coded symbols beyond the number of information symbols required to achieve decoding completion with high probability is linear in k This work considers a new class of random codes which have the following advantages i the overhead is constant in the range of 5 to 10 independent of the number of data symbols being encoded ii the probability of completing decoding for such an overhead is essentially one iii the codes are effective for a number of information symbols as low as a few tens iv the only probability distribution required is the uniform distribution The price for these properties is that the decoding complexity is greater on the order of k 3/2 However for the lower values of k where these codes are of particular interest this increase in complexity might be outweighed by their advantages The parity check matrices of these codes are chosen at random as windowed matrices ie for each column an initial starting position of a window of length w is chosen and the succeeding w positions are chosen at random as zero or one It can be shown that it is necessary that w=Ok 1/2 for the probabilistic matrix rank properties to behave as a nonwindowed random matrix The sufficiency of the condition has so far been established by extensive simulation although other arguments strongly support this conclusion The properties of the codes described depend heavily on the rank properties of random matrices over finite fields Known results on such matrices are briefly reviewed and several conjectures needed in the discussion of the code properties are stated The likelihood of the validity of the conjectures is supported through extensive experimentation Mathematical proof of the conjectures would be of great value for their own interest as well of the particular coding application described here

Keywords:

References

.
Search In Abstract Of Papers:
Other Papers In This Journal:
  1. On Minimum Sum of Radii and Diameters Clustering
  2. Integer Representation and Counting in the Bit Probe Model
  3. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
  4. New Approximation Algorithms for Minimum Cycle Bases of Graphs
  5. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
  6. Aligning Two Convex Figures to Minimize Area or Perimeter
  7. Introduction for S.I. AofA14
  8. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
  9. Detecting Regular Visit Patterns
  10. Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
  11. On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
  12. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
  13. Optimal Parallel Quantum Query Algorithms
  14. Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges
  15. Maximum Series-Parallel Subgraph
  16. A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  17. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
  18. The Parameterized Complexity of Local Search for TSP, More Refined
  19. Approximating Fixation Probabilities in the Generalized Moran Process
  20. Approximation Algorithms for Scheduling with Reservations
  21. Algorithms for the Homogeneous Set Sandwich Problem
  22. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
  23. Computing Minimum Cuts by Randomized Search Heuristics
  24. Constructing Labeling Schemes through Universal Matrices
  25. An Approximation Algorithm for the Minimum Co-Path Set Problem
  26. Scheduling with an Orthogonal Resource Constraint
  27. Approximate Boyer-Moore String Matching for Small Alphabets
  28. Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
  29. Between Treewidth and Clique-Width
  30. What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid
  31. Multi-sided Boundary Labeling
  32. A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
Search Result: