A time improvement over the Mycielski algorithm for predictive signal coding: Mycielski-78


14th European Signal Processing Conference, EUSIPCO 2006, Florence, Italy, 4 - 08 September 2006 identifier

  • Publication Type: Conference Paper / Full Text
  • City: Florence
  • Country: Italy
  • Anadolu University Affiliated: Yes


The Mycielski algorithm is commonly known for applications requiring high quality predictions due to its infinite-past rule based prediction method. Since it repeatedly searches from the beginning of the data source, the complexity becomes non-polynomial, resulting in a limited practical use in multimedia applications, including coding. In this work, we present a time improvement over the Mycielski method by incorporating a codebook for the search which is dynamically constructed during the coding process. The construction method is symmetrical in the encoder and de-coder parts, therefore reconstruction is assured. The idea and strategy resembles the time improvement of the celebrated LZ-78 method over the LZ-77 compression method, where the non-polynomial search is shortened by incorporating a codebook. Analogously, we call the faster method proposed here, the Mycielski-78 method.