应用于低密度奇偶校验解码器之回旋比较方法

摘要

本发明提供一种应用于低密度奇偶校验解码器之回旋比较方法，其系在应用奇偶校验检查码(Low density parity check code,LDPC)之解码器中使用比较器，此比较器利用回旋比较演算法，从输入之k个元素中依序去除第n个元素，n＝1...k－1，组成k个第一串列后，再将k个元素依次两两组合在一起，反覆组合k×log2(k－1)次直到组成k个结束串列，此结束串列与第一串列中皆包含k－1个元素，比较两者是否相同，若相同则结束，若不相同则重新组合出结束串列。利用此种回旋比较之方法只需比较k×log2(k－1)次即可取得结束串列，减少基本比较运算的次数，且任何数目之输入皆适用，亦程式化且接近最佳解。

主权项

1.一种用于低密度奇偶校验码之回旋比较方法，其系在一查核节点单元中输入k个元素，并对该等元素进行比较，该比较方法包括下列步骤：(a)依序去除第一个位置至第k个位置之该元素，取得k个包含k－1个该元素之第一串列，输出该第一串列及每一该第一串列中之一最小值；(b)从该查核节点单元所输入之k个该元素中依序选取二该元素，组成k个第二串列，再依序将二该第二串列组合成k个第三串列；(c)将该第三串列两两组合成复数串列，直到该串列又组成k个包含有k－1个该元素之结束串列；以及(d)比较步骤(c)中该结束串列与步骤(a)中输出之该第一串列是否相同，若相同则结束，并输出每一该结束串列之一最小值，若不相同则重复步骤(c)，重新将该第三串列两两组合成复数该串列，直到该结束串列与该第一串列相同。 ;2.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，其中该元素之值系大于零。 ;3.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，其中该第二串列及该第三串列中该元素之数量皆为偶数。 ;4.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，当k为偶数时，该结束串列系由重复一该元素之二串列所组成，使该结束串列具有奇数个该元素。 ;5.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，其中该第一串列中之具有一第二小值的一位置系以该最小值来取代该第二小值，除该位置以外之该元素值则设为1。 ;6.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，其中该复数第一串列系组成一校验矩阵。 ;7.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，其中该该第二串列、该第三串列、该结束串列及该第三串列组成该结束串列过程中所产生之复数串列，其组合与比较系于复数比较器中完成。 ;8.如申请专利范围第7项所述之用于低密度奇偶校验码之回旋比较方法，其中该比较器之数目为k×log2(k－1)。 ;9.如申请专利范围第7项所述之用于低密度奇偶校验码之回旋比较方法，其中该比较器系输出该最小值。 ;10.如申请专利范围第1项所述之用于低密度奇偶校验码之回旋比较方法，其中每一该结束串列所经过之比较组合次数为log2(k－1)次。;第一图为低密度奇偶校验解码器之流程图。;第二图为低密度奇偶校验解码器之架构图。;第三图为本发明中应用于低密度奇偶校验解码器之第一串列产生之流程图。;第四图为本发明中应用于低密度奇偶校验解码器之回旋比较之示意图。