基于不对称划分模式的高效视频编码加法树并行实现方法

摘要

基于不对称划分模式的高效视频编码加法树并行实现方法涉及数字视频编解码技术领域。本发明采用二维处理元阵列结构，对亮度块分割模式的SAD值计算并行处理，有效的提升了运动估计运算效率。通过采用根据该SAD值后续是否被使用选取存储该SAD值的PE的方法，加快加法树的计算速度，提高计算效率。通过采用单PE存储4×4像素块的方式，相对于传统的像素块的存储方式(单PE存储单像素)，处理单元使用的数量缩减至原来的1/16。相对于加法树串行结构的实现方法，该并行结构速度提高了近92倍。三十六种分块模式SAD值的计算均通过4×4分块模式的SAD值合并得到的，可以减少过多的计算过程，提高计算效率。

说明书

技术领域

本发明涉及数字视频编解码技术领域，特别是高效视频编码(HighEfficiency VideoCoding，简称HEVC)中的整像素运动估计方法。

背景技术

运动估计是视频编码和视频处理中广泛使用的技术。运动估计的基本思想是由 于活动图像邻近帧中的景物存在一定的相关性，因此可以将图形中的每一帧分成互不重叠 的块，并且认为块中所有像素的位移量都相同。然后设法搜出每一个块在邻近帧中的位置， 并且得出两者在空间位置的相对偏移量，得到的相对偏移量就是通常所说的运动矢量，得 到运动矢量的过程就被称为运动估计。

随着视频质量不断提高H.264已经不能满足压缩要求，因此2013年1月26号 HEVC正式成为国际上最新的视频压缩标准。但是运动估计传统的SAD运算体系结构通常 会采用和最大编码块像素相同的运算阵列来进行运算，例如针对H.264的运动估计架构， 宏块大小为16×16像素，因此进行运动估计的SAD运算单元阵列为256个运算单元。 而对于HEVC而言，最大编码块尺寸为64×64像素，如若采用相同或者类似的设计架 构，则需要4096个运算单元，仅在SAD运算这一部分，其面积是H.264的架构的16倍， 从而硬件面积大大增加。

因此研究并设计能够支持HEVC视频编码标准的整数运动估计的SAD加法 树结构，并不是套用原有的架构，而是要重新设计其架构。该架构可以满足64×64块的 SAD计算，并且没有增加硬件面积。

发明内容

本发明所要解决的技术问题是提供一种基于不对称划分模式的高效视频编码加 法树并行实现方法，以提升SAD值的计算效率。

为实现上述目的，本发明所采用的技术方法如下：

基于不对称划分模式的高效视频编码加法树并行实现方法，根据像素块之间的 数据相关性，在邻接互连的二维处理元阵列上，通过使用18*17个处理元完成64×64亮 度块三十七种分块模式的SAD值计算的并行处理，其中处理元即PE包括：

步骤1加法树模块(2)经由缓存区1(2)和缓存区2(2)从外存加载64×64 亮度块(3)，并且以4×4大小的像素块按照(5)的存储方式(自上到下、从左到右) 存放到PE阵列中，每个处理元即PE存放一个4×4大小的亮度块,该方法具体包括：

首先将64×64的亮度块，分成大小为32×64的两部分(7)，分别通过缓存 区1和缓存区2加载到处理元阵列中。

步骤2加法树模块经由缓存区1和缓存区2从外存中读取64×64参考块(4)， 并且以4×4大小的像素块按照(6)的存储方式(自上到下、从左到右)，存放到PE阵 列中，每个处理元(PE)存放一个4×4大小的参考块，该方法具体包括：

首先将64×64的参考块，分成大小为32×64的两部分(7)，分别通过缓存 区1和缓存区2加载到处理元阵列中。

步骤3处理元阵列(2)中的各个PE，在获取的亮度块和参考块的基础上，根 据公式(1)同时计算4×4分块模式SAD值(SAD4×4)，计算完成后存放到亮度块和 参考块对应的PE中，一共256个SAD4×4值，该方法具体包括：

$SAD(i,j)=\underset{m=1}{\overset{M}{\Sigma }}\underset{n=1}{\overset{N}{\Sigma }}|f_k(m,n)-f_{k-1}(m+i,n+j)|---\left(1\right)$

其中f_k(m,n)为当前帧中当前块的亮度值，f_k-1(m+i,n+j)为参考帧中偏 移位置为(i,j)参考块的亮度值。

a大小为4×4的亮度块和4×4的参考块，按照(9)存储到PE中，c0-c15表 示亮度块,d0-d15表示参考块。

bc0与d0做差值并取绝对值、c1与d1做差值并取绝对值，依次类推直到c15 与d15做差值并取绝对值。

c将步骤b得到的16个值求和，得到4×4分块模式的SAD值SAD4×4。

d256个处理元同时执行上述操作，得到256个SAD4×4的值，并且存储到亮 度块和参考块对应的PE中。

步骤4在步骤3计算得到的SAD4×4的基础上进行剩下的三十六种分块模式的 SAD值的计算，并且选择存储该SAD值PE的位置。根据该SAD值是否后续被使用采取如图 8所示的方式选取存储PE的位置，如果该SAD值后续被使用则优先选取PE阵列中右下方 的PE来存储该值，反之则选取左上方的PE来存储该值。具体执行原则如下：如图10所 示每一个字符对应一个4×4块的SAD值，故整体可以得到16×16块的SAD值。首先求8 ×4块的SAD值，即分块模式AB、CD、EF、GH、IJ、KL、MN、OP的SAD值，然后为它们分 别选取存取位置，以AB、EF为例说明，在求8×8分块模式ABEF的SAD值时，我们需要 使用AB和EF的SAD值SAD8×4，由此判定它们的值在后续会被使用，故将它们分别存储 到右边的处理元B和F中，当求分块模式ABEF的SAD值时，B中的SAD8×4传递到F中， F中的两个SAD值求和得到8×8块的SAD值，以此类推其他分块模式的SAD值采用上述方 式选择存储位置，数值往一个方向集中，有利于数值的合并。

a(10)中每个字符代表一个存储SAD4×4值的处理元，4×4个处理元表示 一个簇，处理元阵列可以被划分成16个簇(11)，每个数字代表一个簇。

b每个簇计算得到十四种分块模式的SAD值，它们分别是8×4、4×8、8×8、 16×8、8×16、12×16L、4×16L、12×16R、4×16R、16×12U、16×4U、16×12D、16 ×4D、16×16,计算完成后分别存储到簇内的对应PE中，PE的选取规则如图8所示，即 根据后续是否被使用选取SAD值的存储位置，上述SAD值均通过4×4分块模式的SAD 值合并得到。

c16个簇同时执行b操作；

将16个簇(11)以2×2大小，划分成4个组，第一组(00、01、04、05)， 第二组(02、03、06、07)，第三组(08、09、12、13)，第四组(10、11、14、15)。

每个组可以计算得到11种分块模式的SAD值，如图12所示以第一组00、01、 04、05为例，通过数据交互，可以得到的SAD值分别是32×16、16×32、24×32L、8× 32L、24×32R、8×32R、32×24U、32×8U、32×24D、32×8D、32×32，计算完成后 分别存储到组内对应的PE中，PE的选取规则如图8所示，即根据后续是否被使用选取SAD 值的存储位置，上述SAD值均通过4×4-16×16分块模式的SAD值合并得到。

f四个组同时执行上述操作；

g将16个簇看做一个类(13)。

h该类可以计算得到11种SAD值，它们分别是64×32、32×64、48×64L、 16×64L、48×64R、16×64R、64×48U、64×16U、64×48D、64×16D、64×64，计算 完成后分别存储到类内对应的PE中，PE的选取规则如图8所示，即根据后续是否被使用 选取SAD值的存储位置，上述SAD值均通过16×16-32×32分块模式的SAD值合并得到。

本发明的有益效果如下：

采用二维处理元阵列结构，对亮度块分割模式的SAD值计算并行处理，有效的 提升了运动估计运算效率。通过采用根据该SAD值后续是否被使用选取存储该SAD值的处 理元的方法，加快加法树的计算速度，提高计算效率。

通过采用单PE存储4×4像素块的方式，相对于传统的像素块的存储方式(单 PE存储单像素)，处理单元使用的数量缩减至原来的1/16。

相对于加法树串行结构的实现方法，该并行结构速度提高了近92倍。

步骤4所述的三十六种分块模式SAD值的计算均通过4×4分块模式的SAD值 合并得到的，可以减少过多的计算过程，提高计算效率。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，用来解释本 发明，并不构成对本发明的限制。

在附图中：

图1为本发明提供的PE邻接互连示意图；

图2为本发明提供的加法树阵列和缓存区分布示意图；

图3为本发明提供的亮度块像素分布图；

图4为本发明提供的参考块像素分布图；

图5为本发明提供的亮度块在PE阵列中的存储分布图；

图6为本发明提供的参考块在PE阵列中的存储分布图；

图7为本发明提供的利用双缓存区将图像数据从外存读入PE阵列的示意图

图8为本发明提供的SAD值数据流向图

图9为本发明提供的亮度块和参考块在单个PE中的存储分布图

图10为本发明提供的SAD4×4在单个簇中的存储分布图

图11为本发明提供的PE组在PE阵列中的分布图；

图12为本发明提供的单个PE组在PE阵列具体分布图；

图13为本发明提供的PE类在PE阵列中的分布图；

具体实施方式

以下结合附图对本发明的原理和特征进行描述，所举实例只用于解释本发明， 并非用于限定本发明的范围。

以下实施例提供了一种基于二维阵列处理元的全新高效的包含非对称分割模式 的加法树实现方法,

图1是PE邻接互连示意图，加法树是在该二维邻接互连PE阵列上实现的；

图2是加法树阵列和缓存区分布示意图，灰色部分是缓存区模块(最左边一列 是缓存区1，最右边一列是缓存区2，最下边一行是缓存区3)，中间16×16个PE是加法 树模块，一共采用了18×17个PE；

步骤一将64×64亮度块通过缓存区1和缓存区2读入加法树模块，具体实施 方式如下：

图3是亮度块像素分布图，将亮度块像素划分成两个32×64的像素块，如图7 所示，缓存区1根据地址读取左侧的像素块，缓存区2根据地址读取右侧的像素块，两个 缓存区并行执行，从而提高了传递效率。

通过缓存区传递数据，像素块按照图5所示的方式存储到PE阵列，每个PE存 储4×4大小的像素块，按照从左到右、从上到下的顺序依次存储。

步骤二将64×64参考块通过缓存区1和缓存区2读入加法树模块，具体实施 方式如下：

图4是参考块像素分布图，将参考块数据划分成两个32×64的像素块，如图7 所示，缓存区1根据地址读取左侧的像素块，缓存区2根据地址读取右侧的像素块，两个 缓存区并行执行，从而提高了传递效率。

通过缓存区传递数据，像素块按照图6所示的方式存储到PE阵列，每个PE存 储4×4大小的像素块，按照从左到右、从上到下的顺序依次存储。

步骤三处理元阵列(2)中的各个PE，在获取的亮度块和参考块的基础上，根 据公式(1)同时计算4×4分块模式SAD值(SAD4×4)，计算完成后存放到亮度块和 参考块对应的PE中，一共256个SAD4×4值。

$SAD(i,j)=\underset{m=1}{\overset{M}{\Sigma }}\underset{n=1}{\overset{N}{\Sigma }}|f_k(m,n)-f_{k-1}(m+i,n+j)|---\left(1\right)$

其中其中f_k(m,n)为当前帧中当前块的亮度值，f_k-1(m+i,n+j)为参考帧 中对应偏移位置为(i,j)参考块的亮度值。

a图9为亮度块和参考块在单个PE中的存储分布图，每个PE中存储一个4×4 大小的亮度块和4×4大小的参考块,c0-c15表示亮度块,d0-d15表示参考块；

bc0与d0做差值并取绝对值、c1与d1做差值并取绝对值，以此类推直到c15 与d15做差值并取绝对值。

c将步骤b得到的16个绝对值求和，得到4×4分块模式的SAD值SAD4×4， 然后存储到当前PE中。

d256个处理元同时执行上述操作，得到256个SAD4×4的值，并且存储到4 ×4亮度块和4×4参考块对应的同一个PE中。

步骤四在步骤三得到的SAD4×4的基础上进行剩下的三十六种分块模式的 SAD值计算，然后为得到的SAD值选择存储该值的PE。

根据该SAD值是否后续被使用采取如图8所示的方式选取存储PE的位置，如 果该SAD值后续被使用则优先选取PE阵列中右下方的PE来存储该值，反之则选取左上方 的PE来存储该值。具体执行原则如下：如图10所示每一个字符对应一个4×4块的SAD 值，故整体可以得到16×16块的SAD值。首先求8×4块的SAD值，即分块模式AB、CD、 EF、GH、IJ、KL、MN、OP的SAD值，然后为它们分别选取存取位置，以AB、EF为例说明， 在求8×8分块模式ABEF的SAD值时，我们需要使用AB和EF的SAD值SAD8×4，由此判 定它们的值在后续会被使用，故将它们分别存储到右边的处理元B和F中，当求分块模式 ABEF的SAD值时，B中的SAD8×4传递到F中，F中的两个SAD值求和得到8×8块的SAD 值，以此类推其他分块模式的SAD值采用上述方法选择存储位置，数值往一个方向集中， 有利于数值的合并。具体执行过程如下：

图10为4×4分块模式SAD4×4在单个簇中的存储分布图，图(10)中每个字 符代表一个存储SAD4×4值的处理元，4×4个处理元表示一个簇，处理元阵列一共256 个PE，可以被划分成16个簇，具体为00、01、02、03、04、05、06、07、08、09、10、 11、12、13、14、15，每个数字代表一个簇。具体划分方式如图(11)所示

第一步每个簇计算得到十四种分块模式的SAD值，它们分别是8×4、4×8、 8×8、16×8、8×16、12×16(L)、4×16(L)、12×16(R)、4×16(R)、16×12(U)、16×4(U)、 16×12(D)、16×4(D)、16×16,计算完成后分别存储到簇内的对应PE中，PE的选取规则 如8所示，即根据该SAD值后续是否被使用选取PE，上述SAD值均通过4×4分块模式 的SAD值得到，具体过程如下：

图(10)表示SAD4×4在一个簇内的存储分布图，字母A、B、C、D、E、F、 G、H、I、J、K、L、M、N、O、P分别代表一个PE，每个PE里面存储一个SAD4×4值。

a计算分块模式SAD4×8的值，一共8个块，分别是AE、BF、CG、DH、 IM、JN、KO、LP，具体执行操作以AE为例，首先判断该值是否后续会被使用，SAD4 ×8会在计算8×8分块模式的SAD值SAD8×8时被使用，故应该选取下边的PE作为存 储的位置。然后开始数据传递，A中的SAD4×4通过A->E传递到E中，两个SAD4×4 相加得到SAD4×8，最后将SAD4×8存储到E中。以此类推其余七个块在同一时刻执行 同样操作，单个簇的4×8分块模式的值SAD4×8计算完成。

b计算分块模式SAD8×4的值，一共8个块，分别是AB、CD、EF、GH、 IJ、KL、MN、OP，具体执行操作以AB为例，首先判断该值是否后续会被使用，SAD8 ×4会在计算8×8分块模式的SAD值SAD8×8时被使用，故应该选取右边的PE作为存 储的位置，然后开始数据传递，A中的SAD4×4通过A->B传递到B中，两个SAD4×4 相加得到SAD8×4，最后将SAD8×4存储到B中。以此类推其余七个块在同一时刻执行 同样操作，单个簇的8×4分块模式的值SAD8×4计算完成。

c计算分块模式SAD8×8的值，一共4个块，分别是ABEF、CDGH、IJMN、 KLOP，具体执行操作以ABEF为例，首先判断该值是否后续会被使用，SAD8×8在计算 16×8分块模式的SAD值SAD16×8时被使用，故应该选取右下方的PE作为存储的位置。 然后开始数据传递，B中的SAD8×4通过B->F传递到F中，两个SAD8×4相加得到SAD8 ×8，最后将SAD8×8存储到F中。以此类推其余三个块在同一时刻执行同样操作，单个 簇的8×8分块模式的值SAD8×8计算完成。

d计算分块模式SAD16×8的值，一共2个块，分别是ABEFCDGH、IJMNKLOP， 具体执行操作以ABEFCDGH为例，首先判断该值是否后续会被使用，SAD16×8会在计 算16×16分块模式的SAD值SAD16×16时被使用，故应该选取右边的PE作为存储的位 置。然后开始数据传递，F中的SAD8×8通过F->G->H传递到H中，两个SAD8×8相加 得到SAD16×8，最后将SAD16×8存储到H中。以此类推其余一个块在同一时刻执行同 样操作，单个簇的16×8分块模式的值SAD16×8计算完成。

e计算分块模式SAD8×16的值，一共2个块，分别是ABEFIJMN、CDGHKLOP， 具体执行操作以ABEFIJMN为例，首先判断该值是否后续会被使用，SAD8×16会在计算 16×16分块模式的SAD值SAD16×16时被使用，故应该选取下边的PE作为存储的位置。 然后开始数据传递，F中的SAD8×8通过F->J->N传递到N中，两个SAD8×8相加得到 SAD8×16，最后将SAD8×16存储到N中。依次类推其余一个块在同一时刻执行同样操 作，单个簇的8×16分块模式的值SAD8×16计算完成。

f计算分块模式12×16(L)、12×16(R)、16×12(U)、16×12(D)、4×16(L)、4 ×16(R)、16×4(U)、16×4(D)的SAD值，12×16(L)、12×16(R)、16×12(U)、16×12(D)， 上述4种分块模式可以在同一时刻执行，分块模式4×16(L)、4×16(R)、16×4(U)、16 ×4(D)，这4种分块模式可以在同一时刻执行，然后判断上述8种SAD值在后续不会被使 用，故选取左上角PE作为存储位置，具体过程如下：

g分块模式SAD12×16(L)的计算过程，即BFJNCGKODHLP：首先判断SAD12 ×16(L)在后续过程不会被使用故选取左边的PE作为存储位置，然后开始数据传递，P中 的SAD8×16通过P->O->N传递到N中、F中的SAD4×8通过F->J->N传递到N中，数 据传递完成开始合并数据，在N中将N接收的SAD4×8和本身存储的SAD4×8相加得到 SAD4×16，将SAD4×16和接收的SAD8×16相加得到SAD12×16(L),存储到N中。

h分块模式SAD4×16(L)的计算过程，即AEIM：首先判断SAD4×16(L)在后 续过程不会被使用故选取上边的PE。然后开始数据传递，M中的SAD4×8通过M->I->E 传递到E中，在E中将E接收的SAD4×8和本身存储的SAD4×8相加得到SAD4×16(L), 存储到E中。

i分块模式SAD12×16(R)的计算过程，即AEIMBFJNCGKO：首先判断SAD12 ×16(R)在后续过程不会被使用故选取左边的PE作为存储位置，但是由于N在先前已经被 使用，故选取O作为存储SAD12×16(R)的处理元。然后开始数据传递，G中的SAD4×8 通过G->K->O传递到O中、N中的SAD8×16通过N->O传递到O中，数据传递完成开 始合并数据，在O中将O接收的SAD4×8和本身存储的SAD4×8相加得到SAD4×16， 将SAD4×16和接收的SAD8×16相加得到SAD12×16(R),存储到O中。

j分块模式SAD4×16(R)的计算过程，即DHLP：首先判断SAD4×16(R)在后续 过程不会被使用故选取上边的PE。然后开始数据传递，P中的SAD4×8通过P->L->H传 递到H中，在H中将H接收的SAD4×8和本身存储的SAD4×8相加得到SAD4×16(R), 存储到H中。

k分块模式SAD16×12(U)的计算过程，即EFGHIJKLMNOP：首先判断SAD16 ×12(U)在后续过程不会被使用故选取上边的PE作为存储位置。然后开始数据传递，F中 的SAD8×4通过F->G->H传递到H中、P中的SAD16×8通过P->L->H传递到H中，数 据传递完成开始合并数据，在H中将H接收的SAD8×4和本身存储的SAD8×4相加得到 SAD16×4，将SAD16×4和接收的SAD16×8相加得到SAD16×12(U),存储到H中。

l分块模式SAD16×4(U)的计算过程，即ABCD：首先判断SAD16×4(U)在后 续过程不会被使用故选取左边的PE。然后开始数据传递，D中的SAD8×4通过D->C->B 传递到B中，在B中将B接收的SAD8×4和本身存储的SAD8×4相加得到SAD16×4(U), 存储到B中。

m分块模式SAD16×12(D)的计算过程，即ABCDEFGHIJKL：首先判断SAD16 ×12(D)在后续过程不会被使用故选取上边的PE作为存储位置。但是由于H在先前已经被 使用，故选取L作为存储SAD16×12(D)的处理元。然后开始数据传递，J中的SAD8×4 通过J->K->L传递到L中、H中的SAD16×8通过H->L传递到L中，数据传递完成开始 合并数据，在L中将L接收的SAD8×4和本身存储的SAD8×4相加得到SAD16×4，将 SAD16×4和接收的SAD16×8相加得到SAD16×12(D),存储到L中。

n分块模式SAD16×4(D)的计算过程，即MNOP：首先判断SAD16×4(D)在后 续过程不会被使用故选取左边的PE。然后开始数据传递，P中的SAD8×4通过P->O->N 传递到N中，在N中将N接收的SAD8×4和本身存储的SAD8×4相加得到SAD16×4(D), 存储到N中。

o计算分块模式SAD16×16的值，一共1个块，即ABCDEFGHIJKLMNOP， 具体执行操作为首先判断该值是否后续会被使用，SAD16×16会在计算分块模式SAD32 ×16时被使用，故应该选取右下方的PE作为存储的位置。然后开始数据传递，H中的 SAD16×8通过H->L->P传递到P中，两个SAD16×8相加得到SAD16×16，最后将SAD16 ×16存储到P中，单个簇的16×16分块模式的值SAD16×16计算完成。

p图11中的16个簇同时执行上述过程，计算完成14种分块模式的SAD值的 运算。

按照图11所示把2×2个簇划分成一个组，一共四个组。00、01、04、05是第 一组，02、03、06、07是第二组，08、09、12、13是第三组，10、11、14、15是第四组；

第二步每个组计算得到十一种分块模式的SAD值，它们分别是32×16、16 ×32、24×32(L)、8×32(L)、24×32(R)、8×32(R)、32×24(U)、32×8(U)、32×24(D)、 32×8(D)、32×32,计算完成后分别存储到组内的对应PE中(PE的选取规则如(8)所示， 即根据后续是否被使用选取的)，上述SAD值均通过第一步计算得到的分块模式4×4-16 ×16的SAD值合并得到；

图(12)表示第一个组内各个PE的分布，字母00A-00P指的是00簇内的各个 位置上的PE，字母01A-01P指的是01簇内的各个位置上的PE，字母04A-04P指的是04 簇内的各个位置上的PE，字母05A-05P指的是05簇内的各个位置上的PE。簇内的各个 PE存储了第一步执行完成后分块模式4×4-16×16的SAD值。

a计算分块模式SAD32×16的值，一共2个块，分别是00A00B…… 00P(00)01A01B……01P(01)、04A04B……04P05A05B……05P，具体执行操作以 00A00B……00P01A01B……01P为例，首先判断该值是否后续会被使用，SAD32×16会在 计算分块模式SAD32×32时被使用，故应该选取右边的PE作为存储的位置。然后开始数 据传递，00P(00簇)中的SAD16×16通过00P->01M->01N->01O->01P传递到01P(01簇) 中，两个SAD16×16相加得到SAD32×16，最后将SAD32×16存储到01P中。以此类推 剩下一个块在同一时刻执行同样操作，单个组的32×16分块模式的值SAD32×16计算完 成。

b计算分块模式SAD16×32的值，一共2个块，分别是00A00B…… 00P(00)04A04B……04P(04)、01A01B……01P05A05B……05P，具体执行操作以 00A00B……00P04A04B……04P为例，首先判断该值是否后续会被使用，SAD16×32会在 计算分块模式SAD32×32时被使用，故应该选取下边的PE作为存储的位置。然后开始数 据传递，00P(00簇)中的SAD16×16通过00P->04D->04H->04L->04P传递到04P(04簇)中， 两个SAD16×16相加得到SAD16×32，最后将SAD16×32存储到04P中。以此类推剩下 一个块在同一时刻执行同样操作，单个组的16×32分块模式的值SAD16×32计算完成。

c计算分块模式24×32(L)、24×32(R)、32×24(U)、32×24(D)、8×32(L)、 8×32(R)、32×8(U)、32×8(D)的SAD值，24×32(L)、24×32(R)、32×24(U)、32×24(D)， 上述4种分块模式可以在同一时刻执行，分块模式8×32(L)、8×32(R)、32×8(U)、32 ×8(D)，这4种分块模式可以在同一时刻执行，然后判断上述8种SAD值在后续不会被使 用，故选取左上角PE作为存储位置；具体过程如下

d分块模式SAD24×32(L)的计算过程：

00C00D00G00H00K00L00O00P04C04D04G04H04K04L04O04P

01A01B……01P(01)05A05B……05P(05)块，首先判断SAD24×32(L)在后续过程不会被使 用故选取左边的PE作为存储位置。然后开始数据传递，05P(05)中的SAD16×32通过 05P->05O->05N->05M->04P传递到04P中、00P(00)中的SAD8×16通过 00P->04D->04H->04L->04P传递到04P(04)中，数据传递完成开始合并数据，在04P中将 04P接收的SAD8×16和本身存储的SAD8×16相加得到SAD8×32，将SAD8×32和接 收的SAD16×32相加得到SAD24×32(L),存储到04P中。

e分块模式SAD8×32(L)的计算过程， 00A00B00E00F00I00J00M00N04A04B04E04F04I04J04M04N块，首先判断SAD8×32(L)在 后续过程不会被使用故选取上边的PE。然后开始数据传递，04N(04)中的SAD8×16通 04N->04J->04F->04B->00N传递到00N(00)中，在00N中将00N接收SAD8×16和本身存 储的SAD8×16相加得到SAD8×32(L),存储到00N中。

f分块模式SAD24×32(R)的计算过程：

01A01B01E01F01I01J01M01N05A05B05E05F05I05J05M05N

00A00B……00P(00)04A04B……04P(04)块，首先判断SAD24×32(R)在后续过程不会被使 用故选取左边的PE作为存储位置。然后开始数据传递，04P(04)中的SAD16×32通过 04P->05M->05N传递到05N(05)中、01N(01)中的SAD8×16通过 01N->05B->05F->05J->05N传递到05N(05)中，数据传递完成开始合并数据，在05N中将 05N接收的SAD8×16和本身存储的SAD8×16相加得到SAD8×32，将SAD8×32和接 收的SAD16×32相加得到SAD24×32(R),存储到05N(05)中。

g分块模式SAD8×32(R)的计算过程， 01C01D01G01H01K01L01O01P05C05D05G05H05K05L05O05P首先判断SAD8×32(R)在后 续过程不会被使用故选取上边的PE。然后开始数据传递，05P(05)中的SAD8×16通 05P->05L->05H->05D->01P传递到01P(01)中，在01P中将01P接收SAD8×16和本身存 储的SAD8×16相加得到SAD8×32(R),存储到01P中。

h分块模式SAD32×24(U)的计算过程：

00I00J00K00L00M00N00O00P01I01J01K01L01M01N01O01P

04A04B……04P(04)05A05B……05P(05)块，首先判断SAD32×24(U)在后续过程不会被使 用故选取上边的PE作为存储位置。然后开始数据传递，05P(05)中的SAD32×16通过 05P->05L->05H->05D->01P传递到01P(01)中、00P(00)中的SAD16×8通过 00P->01M->01N->01O->01P传递到01P(01)中，数据传递完成开始合并数据，在01P中将 01P接收的SAD16×8。和本身存储的SAD16×8相加得到SAD32×8，将SAD32×8和接 收的SAD32×16相加得到SAD32×24(U),存储到01P中。

I分块模式SAD32×8(U)的计算过程， 00A00B00C00D00E00F00G00H01A01B01C01D01E01F01G01H首先判断SAD32×8(U)在后 续过程不会被使用故选取左边的PE。然后开始数据传递，01H(01)中的SAD16×8通 01H->01G->01F->01E->00H传递到00H(00)中，在00H中将00H接收SAD16×8和本身存 储的SAD16×8相加得到SAD32×8(U),存储到00H中。

j分块模式SAD32×24(D)的计算过程:

04A04B04C04D04E04F04G04H05A05B05C05D05E05F05G05H

00A00B……00P(00)01A01B……01P(01)块，首先判断SAD32×24(D)在后续过程不会被使 用故选取上边的PE作为存储位置。然后开始数据传递，01P(01)中的SAD32×16通过 01P->05D->05H传递到05H(05)中、04H(04)中的SAD16×8通过04H->05E>05F->05G->05H 传递到05H(05)中，数据传递完成开始合并数据，在05H中将05H接收的SAD16×8和本 身存储的SAD16×8相加得到SAD32×8，将SAD32×8和接收的SAD32×16相加得到 SAD32×24(D),存储到05H中。

k分块模式SAD32×8(D)的计算过程， 04I04J04K04L04M04N04O04P05I05J05K05L05M05N05O05P首先判断SAD32×8(D)在后 续过程不会被使用故选取左边的PE。然后开始数据传递，05P(05)中的SAD16×8通过 05P->05O->05N->05M->04P传递到04P(04)中，在04P中将04P接收SAD16×8和本身存 储的SAD16×8相加得到SAD32×8(D),存储到04P中。

计算分块模式SAD32×32的值，一共1个块，分别是00A00B…… 00P(00)04A04B……04P(04)01A01B……01P05A05B……05P，具体执行操作：首先判断该 值是否后续会被使用，SAD32×32会在计算分块模式SAD32×64时被使用，故应该选取 右下方的PE作为存储的位置。然后开始数据传递，01P(01)中的SAD32×16通过 01P->05D->05H->05L->05P传递到05P(05簇)中，两个SAD32×16相加得到SAD32×32， 最后将SAD32×32存储到05P中。

图11中的4个组同时执行上述过程，计算完成11种分块模式的SAD值的运 算。

按照图13所示把4×4个簇看做一个类，图中的00、01……15分别代表一个 簇，每个簇中的00p、01p……15p代表簇内的最后一个PE。簇与簇之间的数据交互可以通 过路由器(路由器和簇内的最后一个PE相连)实现(如图1所示)

第三步该类可以计算得到十一种分块模式的SAD值，它们分别是64×32、32 ×64、48×64(L)、16×64(L)、48×64(R)、16×64(R)、64×48(U)、64×16(U)、64×48(D)、 64×16(D)、64×64,计算完成后分别存储到组内的对应PE中(PE的选取规则如(8)所 示，即根据后续是否被使用选取的)，上述SAD值均通过第二步计算得到的分块模式16 ×16-32×32的SAD值合并得到；

a计算分块模式SAD64×32的值，一共2个块，分别是0001020304050607、 0809101112131415，以0001020304050607为例，首先判断该值是否后续会被使用，SAD64 ×32会在计算分块模式SAD64×64时被使用，故应该选取右边的PE作为存储的位置。然 后开始数据传递，05P中的SAD32×32通过路由器传递给07P,在07P中两个SAD32×32 相加得到64×32分块模式的值SAD64×32，将SAD64×32存储到07P中，以此类推剩下 一个块在同一时刻执行同样操作，类中的64×32分块模式的值SAD64×32计算完成。

b计算分块模式SAD32×64的值，一共2个块，分别是0001040508091213、 0203060710111415，以0001040508091213为例，首先判断该值是否后续会被使用，SAD32 ×64会在计算分块模式SAD64×64时被使用，故应该选取下边的PE作为存储的位置。然 后开始数据传递，05P中的SAD32×32通过路由器传递给13P,在13P中两个SAD32×32 相加得到32×64分块模式的值SAD32×64，将SAD32×64存储到13P中，以此类推剩下 一个块在同一时刻执行同样操作，类中的32×64分块模式的值SAD32×64计算完成。

c计算分块模式48×64(L)、48×64(R)、64×48(U)、64×48(D)、16×64(L)、 16×64(R)、64×16(U)、64×16(D)的SAD值，48×64(L)、48×64(R)、64×48(U)、64 ×48(D)，上述4种分块模式可以在同一时刻执行，分块模式16×64(L)、16×64(R)、64 ×16(U)、64×16(D)，这4种分块模式可以在同一时刻执行，然后判断上述8种SAD值 在后续不会被使用，故选取左上角PE作为存储位置；具体过程如下:

d分块模式SAD48×64(L)的计算过程：即010203050607091011131415的计 算过程，首先判断SAD48×64(L)在后续过程不会被使用，故选取左边的PE作为存储位置。 然后开始数据传递，05P中的SAD16×32通过路由器传递到13P中、15P中的SAD32×64 通过路由器传递到13P中，数据传递完成开始合并数据，在13P中将13P接收的SAD16 ×32和本身存储的SAD16×32相加得到SAD16×64，将SAD16×64和接收的SAD32× 64相加得到SAD48×64(L),存储到13P中。

e分块模式SAD16×64(L)的计算过程，即00040812块，首先判断SAD16× 64(L)在后续过程不会被使用故选取上边的PE。然后开始数据传递，12P中的SAD16×32 通过路由器传递到04P中，在04P中将04P接收SAD16×32和本身存储的SAD16×32相 加得到SAD16×64(L),存储到04P中。

f分块模式SAD48×64(R)的计算过程：即000102040506080910121314的计算 过程，首先判断SAD48×64(R)在后续过程不会被使用，故选取左边的PE作为存储位置。 然后开始数据传递，06P中的SAD16×32通过路由器传递到14P中、13P中的SAD32×64 通过路由器传递到14P中，数据传递完成开始合并数据，在14P中将14P接收的SAD16 ×32和本身存储的SAD16×32相加得到SAD16×64，将SAD16×64和接收的SAD32× 64相加得到SAD48×64(R),存储到14P中。

g分块模式SAD16×64(R)的计算过程，即03071115块，首先判断SAD16× 64(R)在后续过程不会被使用，故选取上边的PE。然后开始数据传递，15P中的SAD16× 32通过路由器传递到07P中，在07P中将07P接收SAD16×32和本身存储的SAD16×32 相加得到SAD16×64(R),存储到07P中。

h分块模式SAD64×48(U)的计算过程：即040506070809101112131415的计算 过程，首先判断SAD64×48(U)在后续过程不会被使用故选，取上边的PE作为存储位置。 然后开始数据传递，05P中的SAD32×16通过路由器传递到07P中、15P中的SAD64×32 通过路由器传递到07P中，数据传递完成开始合并数据，在07P中将07P接收的SAD32 ×16和本身存储的SAD32×16相加得到SAD64×16，将SAD64×16和接收的SAD64× 32相加得到SAD64×48(U),存储到07P中。

i分块模式SAD64×16(U)的计算过程，即00010203块，首先判断SAD64×16(U) 在后续过程不会被使用，故选取左边的PE。然后开始数据传递，03P中的SAD32×16通 过路由器传递到01P中，在01P中将01P接收SAD32×16和本身存储的SAD32×16相加 得到SAD64×16(U),存储到01P中。

j分块模式SAD64×48(D)的计算过程：即000102030405060708091011的计算过 程，首先判断SAD64×48(D)在后续过程不会被使用，故选取上边的PE作为存储位置。然 后开始数据传递，07P中的SAD64×32通过路由器传递到11P中、09P中的SAD32×16 通过路由器传递到11P中，数据传递完成开始合并数据，在11P中将11P接收的SAD32 ×16和本身存储的SAD32×16相加得到SAD64×16，将SAD64×16和接收的SAD64× 32相加得到SAD64×48(D),存储到11P中。

k分块模式SAD64×16(D)的计算过程，即12131415块，首先判断SAD64×16(D) 在后续过程不会被使用，故选取左边的PE。然后开始数据传递，15P中的SAD32×16通 过路由器传递到13P中，在13P中将13P接收SAD32×16和本身存储的SAD32×16相加 得到SAD64×16(D),存储到13P中。

l计算分块模式SAD64×64的值，即00010405080912130203060710111415块， 开始数据传递，07P中的SAD64×32通过路由器传递给15P，在15P中两个SAD64×32 相加得到64×64分块模式的值SAD64×64，将SAD64×64存储到15P中。

加法树过程执行结束一共得到37种分块模式的SAD值，一共849个SAD值。