[發(fā)明專利]修正歐幾里德算法的部分并行實(shí)現(xiàn)裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201110052369.3
• 申請(qǐng)日: 2011-03-04
• 公開（公告）號(hào): CN102655443B
• 公開（公告）日: 2016-11-02
• 發(fā)明（設(shè)計(jì)）人: 張玉安
• 申請(qǐng)（專利權(quán)）人: 上海華虹集成電路有限責(zé)任公司
• 主分類號(hào): H04L1/00
• 分類號(hào): H04L1/00
• 代理公司: 上海浦一知識(shí)產(chǎn)權(quán)代理有限公司 31211
• 代理人: 戴廣志

1.一種修正歐幾里德算法的部分并行實(shí)現(xiàn)方法，其特征在于，包括如下步驟：

步驟一、根據(jù)伴隨式的計(jì)算結(jié)果，初始化錯(cuò)誤位置多項(xiàng)式和錯(cuò)誤值多項(xiàng)式，使Q(x)＝S(x)，R(x)＝0，η(x)＝0，μ(x)＝1；其中，R(x)為錯(cuò)誤值多項(xiàng)式，η(x)為錯(cuò)誤位置多項(xiàng)式，S(x)為伴隨多項(xiàng)式，Q(x)和μ(x)分別為計(jì)算錯(cuò)誤值多項(xiàng)式和計(jì)算錯(cuò)誤位置多項(xiàng)式的輔助多項(xiàng)式；

步驟二、將M項(xiàng)所述錯(cuò)誤位置多項(xiàng)式和M項(xiàng)錯(cuò)誤值多項(xiàng)式分為4組，每組內(nèi)包含N項(xiàng)錯(cuò)誤位置多項(xiàng)式和N項(xiàng)錯(cuò)誤值多項(xiàng)式，每個(gè)周期內(nèi)同時(shí)完成N項(xiàng)錯(cuò)誤位置多項(xiàng)式和N項(xiàng)錯(cuò)誤值多項(xiàng)式的并行迭代運(yùn)算，四個(gè)周期完成第一次迭代運(yùn)算，得到錯(cuò)誤位置多項(xiàng)式和錯(cuò)誤值多項(xiàng)式的最高次數(shù)項(xiàng)系數(shù)和控制信號(hào)，繼而進(jìn)行下一次的第二次迭代運(yùn)算；其中，M和N均為大于1的正整數(shù)；

步驟三、在設(shè)定的2t×4個(gè)周期結(jié)束時(shí)，停止迭代運(yùn)算，此時(shí)得到錯(cuò)誤位置多項(xiàng)式和錯(cuò)誤值多項(xiàng)式。

2.如權(quán)利要求1所述的方法，其特征在于：在執(zhí)行步驟一完成初始化后，如果錯(cuò)誤值多項(xiàng)式的最高次數(shù)項(xiàng)系數(shù)a≠0，且Δ＝deg(R)-deg(Q)≥0，則使R(x)和Q(x)相互交換，a和b相互交換，然后再進(jìn)行迭代運(yùn)算，計(jì)算錯(cuò)誤值多項(xiàng)式和錯(cuò)誤位置多項(xiàng)式；否則直接計(jì)算錯(cuò)誤值多項(xiàng)式和錯(cuò)誤位置多項(xiàng)式；其中，a，b分別為R(x)和Q(x)的最高次數(shù)項(xiàng)系數(shù)。

3.一種修正歐幾里德算法的部分并行實(shí)現(xiàn)裝置，其特征在于，包括：

初始化模塊，用于對(duì)錯(cuò)誤值多項(xiàng)式和錯(cuò)誤位置多項(xiàng)式進(jìn)行初始化，使Q(x)＝S(x)，R(x)＝0，η(x)＝0，μ(x)＝1；其中，R(x)為錯(cuò)誤值多項(xiàng)式，η(x)為錯(cuò)誤位置多項(xiàng)式，S(x)為伴隨多項(xiàng)式，Q(x)和μ(x)分別為計(jì)算錯(cuò)誤值多項(xiàng)式和計(jì)算錯(cuò)誤位置多項(xiàng)式的輔助多項(xiàng)式；

并行運(yùn)算單元，與初始化模塊相連接，每個(gè)并行運(yùn)算單元包括16個(gè)組合邏輯運(yùn)算單元，每個(gè)并行運(yùn)算單元在一個(gè)周期內(nèi)完成四分之一錯(cuò)誤值多項(xiàng)式和錯(cuò)誤位置多項(xiàng)式的迭代運(yùn)算，在4個(gè)周期內(nèi)完成所有錯(cuò)誤值多項(xiàng)式和錯(cuò)誤位置多項(xiàng)式的一次迭代運(yùn)算；在每次錯(cuò)誤值多項(xiàng)式迭代運(yùn)算完成后得到錯(cuò)誤值多項(xiàng)式的最高次數(shù)項(xiàng)系數(shù)，同時(shí)一次迭代運(yùn)算完成后進(jìn)行移項(xiàng)操作，將空出的組合邏輯運(yùn)算單元在下一次迭代運(yùn)算時(shí)用于錯(cuò)誤位置多項(xiàng)式的計(jì)算。