ГлавнаяАрхивО списочном декодировании вейвлет-кодов над конечными полями характеристики два

О списочном декодировании вейвлет-кодов над конечными полями характеристики два | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/7

Доказывается, что вейвлет-код над полем GF(2m) c длиной кодовых и информационных слов n = 2m - 1 и (n - 1)/2 соответственно, у которого среди коэффициентов спектрального представления порождающего многочлена имеется d + 1 последовательных нулей, 0 < d < (n - 3)/2, допускает списочное декодирование за полиномиальное время. Шаги алгоритма, осуществляющего списочное декодирование с исправлением до e < n - л/n(n - d - 2) ошибок, реализованы в виде программы. Приведены примеры её применения для списочного декодирования зашумленных кодовых слов. Отмечено, что неравенство Варшамова - Гилберта при достаточно больших n не позволяет судить о существовании вейвлет-кодов c максимальным кодовым расстоянием (n - 1)/2.
  • Title О списочном декодировании вейвлет-кодов над конечными полями характеристики два
  • Headline О списочном декодировании вейвлет-кодов над конечными полями характеристики два
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 44
  • Date:
  • DOI 10.17223/20710410/44/7
Ключевые слова
вейвлет-коды, полифазное кодирование, декодирование спис ком, wavelet codes, polyphase coding, list decoding
Авторы
Ссылки
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1974. 744 c
Fekri F., McLaughlin S. W., Mersereau R. M., and Schafer R. W. Double circulant self-dual codes using finite-field wavelet transforms // Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Berlin: Springer, 1999. P. 355-363
Fekri F., McLaughlin S. W., Mersereau R. M., and Schafer R. W. Error Control Coding using Finite-Field Wavelet Transforms. Atlanta: Center for Signal Image Processing, 1999. 13 p
Daubechies I. Десять лекций по вейвлетам. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 464 c
Mallat S. Wavelet Tour of Signal Processing. 2nd ed. Boston: Academic Press, 1999. 799 p
Phoong S. M. and Vaidyanathan P. P. Paraunitary filter banks over finite fields // IEEE Trans. Signal Processing. 1997. V. 45. No. 6. P. 1443-1457
Fekri F., Mersereau R. M., and Schafer R. W. Theory of paraunitary filter banks over fields of characteristic two // IEEE Trans. Inform. Theory. 2002. V. 48. No. 11. P. 2964-2979
Fekri F. and Delgosha F. Finite-Field Wavelet Transforms with Applications in Cryptography and Coding. Upper Saddle River: Prentice Hall, 2010. 304p
Caire G., Grossman R. L., and Poor H. V. Wavelet transforms associated with finite cyclic groups // IEEE Trans. Inform. Theory. 1993. V. 39. No. 4. P. 1157-1166
Fekri F., Mersereau R. M., and SchaferR.W. Theory ofwavelet transform over finite fields // Proc. IEEE Intern. Conf. Acoustics, Speech, and Signal Processing. 1999. V. 3. P. 1213-1216
Черников Д. В. Помехоустойчивое кодирование с использованием биортогональных наборов фильтров // Сибирские электрон. матем. известия. 2015. Т. 12. С. 704-713
Doubechies I. and Sweldens W. Factoring wavelet transforms into lifting steps // J. Fourier Anal. Appl. 1998. V. 4. No. 3. P. 247-269
Соловьев А. А., Черников Д. В. Биортогональные вейвлет-коды в полях характеристики два // Челяб. физ.-мат. журн. 2017. Т. 2. № 1. С. 66-79
Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971. 479с
Сидельников В. М. Теория кодирования. М.: Физматлит, 2008. 324с
Berlekamp E. R. and Welch L. R. Error Correction of Algebraic Block Codes. US Patent 4633470A. 30.12.1986
Ромащенко А. Е., Румянцев А. Ю., Шень А. Заметки по теории кодирования. М.: МЦН-МО, 2011. 80с
Sudan M. Decoding of Reed Solomon codes beyond the error-correction bounds // J. Complexity. 1997. V. 13. No. 1. P. 180-193
Guruswami V. and Sudan M. Improved decoding of Reed - Solomon and algebraic-geometric codes // IEEE Trans. Inform. Theory. 1999. V. 45. No. 6. P. 1757-1767
Литичевский Д. В. Списочное декодирование биортогональных вейвлет-кодов с заданным кодовым расстоянием в поле нечётной характеристики // Прикладная дискретная математика. 2018. №39. С. 72-77
Соловьев А А. Комплементарное представление многочленов над конечными полями // Челяб. физ.-мат. журн. 2017. Т. 2. Вып. 2. С. 199-209
О списочном декодировании вейвлет-кодов над конечными полями характеристики два | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/7
О списочном декодировании вейвлет-кодов над конечными полями характеристики два | Прикладная дискретная математика. 2019. № 44. DOI: 10.17223/20710410/44/7