Декодирование низкоплотностных кодов

Рассматривается декодирование кодов с малой плотностью проверок на четность по алгоритму Зяблова–Пинскера. Показано, что переход от мажоритарного декодирования к пороговому повышает реализуемое алгоритмом расстояние при том же порядке сложности. Анализируется вариант алгоритма, ориентированный на машинную реализацию и требующий выполнения порядка $n$ голосований, где $n$ – длина кода.