基于有限域设计的通用概率卷积算法

General Probability Convolution Algorithm over GF(q)

概率卷积在现代数字通信系统等领域具有重要而又基础的作用.首先介绍用于有限域下的概率卷积的组合搜索法和FFT法;然后提出一种基于有限域设计的通用概率卷积算法,基于有限域运算,用递归的求解方法实现提出的通用概率卷积算法.通过算例、实验和比较分析,讨论了三种算法在有限域概率卷积中的优缺点.分析发现在小规模的有限域下的概率卷积,通用法与FFT法相比,计算复杂度相当但更通用;在大规模概率卷积情况下,通用算法比FFT更通用,比组合搜索法更有效.

Probability convolution is an important and basic role in modern digital communication. This paper first introduces com-bination search approach and FFT method for probability convolution over GF（q）. Then, this paper proposes general probability con-volution algorithm over GF（q）. We implement our algorithm, based on the operators in finite field, by using the recursive method. Through an example, experiment comparison and theory analysis, this paper discusses the advantages and defects among the three algo- rithms. In small case of probability convolution, our algorithm＇s computing complexity is the same as FFT, but it is more general. When the scale of probability convolution is larger, our algorithm is more general than FFT, and is more effective than combination search algorithm.