关于线性时间复损码的研究

摘要

本文对基于随机二部图的复损码进行了深入的研究.提出了给定度分布对的复损码成功译码时可接受最大损失δ的一上界,通过对此上界的详细分析提出了求解复损码度分布对的一种算法.这就从理论上说明了具有如上算法选取度分布对的复损码,应该优于文[2]所给度分布对的复损码.而且证明了具有某一确定度分布对的复损码能以线性时间可编码和可成功地译码.