第5章 信源编码
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
第5章 信源编码
信源编码的目的是提高传输有效性，压缩冗余消息，提高编码效率。
冗余原因是信源符号之间存在相关性和概率分布不均匀。
所以，信源压缩编码的基本途径有两个：
使序列中的各个符号尽可能地互相独立，即解除相关性；
使编码后各个符号出现的概率尽可能地相等，即概率均匀化。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
信源编码的作用可归纳为：
(1) 符号变换：使信源的输出符号与信道的输入符号相匹配；
(2)信息匹配：使信息传输率达到信道容量；
(3) 冗余度压缩：使编码效率等于或接近100％。
第5章 信源编码
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
第5章 信源编码
信源编码的基础是信息论中的两个编码定理：
无失真编码定理
限失真编码定理
无失真编码可精确复制信源输出的消息，只适用于离散信源
对于连续信源，只能在失真受限制的情况下进行限失真编码
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
第5章 信源编码
本章讨论离散信源编码，首先从无失真编码定理出发，重点讨论以香农码、费诺码和霍夫曼码为代表的最佳无失真码。然后介绍了限失真编码定理。最后简单介绍了一些其它常用的信源编码方法。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
信源
编码器
信道
码表
图5-1 信源编码器示意图
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
将信源消息分成若干组，即符号序列xi，
xi＝(xi1xi2…xil…xiL)，
xilA={a1，a2，…，ai，…，an}
每个符号序列xi依照固定码表映射成一个码字yi，
yi＝(yi1yi2…yil…yiL)，
yilB={b1，b2，…，bi，…，bm}
这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
如图5-1所示，如果信源输出符号序列长度L＝1，信源符号集A(a1，a2，…，an)
信源概率空间为
若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码 。
如果L=2，码表多大？
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
码可分为两类：
一、固定长度的码，码中所有码字的长度 都相同，如表5-1中的码1就是定长码
二、可变长度码，码中的码字长短不一，如表中码2就是变长码。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
不同的码符号序列，如表5-1所示。
表5-1 变长码与定长码
信源符号ai 信源符号出现概率p(ai) 码表
码1 码2
a1 p(a1) 00 0
a2 p(a2) 01 01
a3 p(a3) 10 001
a4 p(a4) 11 111
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
（1）奇异码和非奇异码
若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。
如表5-2中的码1是奇异码，码2是非奇异码。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
（2）唯一可译码
任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
唯一可译码中又分为非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
即时码：只要收到符号就表示该码字已完整，可以立即译码。
即时码又称为非延长码，任意一个码字都不是其它码字的前缀部分，有时叫做异前缀码。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
信源符号ai 符号出现概率p(ai) 码1 码2 码3 码4
a1 1/2 0 0 1 1
a2 1/4 11 10 10 01
a3 1/8 00 00 100 001
a4 1/8 11 01 1000 0001
码
奇异码
非分组码
分组码
非奇异码
非唯一可译码
非即时码
即时码(非延长码)
唯一可译码
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
通常可用码树来表示各码字的构成
二进制码树
0 1
0 1
0 1
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
0 1 2
0 1 2 0 1 2 0 1 2
0 1 2
0 1 2
三进制码树
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
码树与码字对应关系图
树根
树枝数
节点
终端节点
节数
非满树
满树
码字的起点
码的进制数
码字或码字的一部分
码字
码长
变长码
等长码
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
唯一可译码存在的充分和必要条件
各码字的长度Ki 应符合克劳夫特不等式：
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
例：设二进制码树中X (a1， a2 ， a3 ， a4 )，K1＝1，K2＝2，K3＝2，K4＝3，应用上述判断定理：
因此不存在满足这种Ki的唯一可译码。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
{0，10，110，111} 惟一可译码；
{0，10，010，111}
不是惟一可译码；
均满足克劳夫特不等式
K1＝1，K2＝2，K3＝3，K4＝3
1 0
1 0
1 0
a2=10
a3=110
a4=111
a1=0
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.1 编码的概念
克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
X＝(X1X2…Xl…XL)
Xl{a1,a2,…,ai,…,an}
nL种
用Y表示L长的信源序列X，则送出一个信源符号所需要的信息率平均为
编码目的：使 最小
信源
编码器
Yk{b1,b2,…,bj,…,bm}
M=mKL种
KL log m
5.2 无失真信源编码定理
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.2 无失真信源编码定理
无失真信源编码定理研究的内容:
最小信息率为多少时，才能得到无失真的译码？
若小于这个信息率是否还能无失真地译码?
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.2 无失真信源编码定理
无失真的信源编码定理
定长编码定理
变长编码定理
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
无记忆平稳信源平均符号熵为HL(X)， 只要
则当L足够大时，必可使译码差错足够小；
反之，当 时，译码差错一定是有限值，而L足够大时，译码几乎必定出错。
5.2.1 定长编码定理
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。
反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。
当 时，则为临界状态，可能无失真，也可能有失真。
定长编码定理说明
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
例：信源输出8种符号，
L=1，等概率时，H1(X)＝log2 8＝3比特/符号，可用3比特的信息率进行无失真的编码。
p(ai)＝{0.4，0.18，0.1，0.1，0.07，0.06，0.05，0.04}，则此时H1(X)＝2.55比特/符号，22.55＝5.856
当L足够大，没有对应码字的符号序列发生的概率变得很小，使得差错概率达到足够小。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
式中 为自信息方差
为一正数。当 和 均为定值时，只要L足够大，Pe可以小于任一正数。即，
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
当信源序列长度L满足 时，
能达到差错率要求
在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
定义
为编码效率，即信源的平均符号熵为H(X)，采用平均符号码长为 来编码，所得的效率。
编码效率总是小于1，且最佳编码效率为
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即
L取无限长
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
例5-2 设离散无记忆信源概率空间为
比特/符号
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
对信源符号采用定长二元编码，要求编码效率为 90％，若取L＝1，则可算出
＝2.55 90%=2.8比特/符号
Pe＝0.04 太大
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
若要求译码错误概率
当L有限时，要做到高编码效率、低错误率，对于定长编码来说是不可能做到的。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
平均码长：
根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）
5.2.2变长编码定理
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式
其中为任意小正数。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
编码效率总是小于1，可以用它来衡量各种编码方法的优劣。
为了衡量各种编码方法与最佳码的差距，定义码的剩余度为
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
例5.3设离散无记忆信源的概率空间为
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
编码效率为
输出的信息效率为
R＝0.811比特/二元码符号
续例5.3
若L=1,用二元定长编码(0，1)来构造一个即时码： 。
平均码长 ＝1二元码符号/信源符号
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
当L=2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表
续例5.3
xi p(xi) 即时码
a1a1 9/16 0
a1a2 3/16 10
a2a1 3/16 110
a2a2 1/16 111
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
二元码符号/信源序列
二元码符号/信源符号
编码效率
信息效率 R2＝0.961比特/二元码符号
续例5.3
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
L＝3
R3＝0.985比特/二元码符号
L＝4
R4＝0.991比特/二元码符号
续例5.3
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
定长二元码编码，要求编码效率达到96％时，允许译码错误概率
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
香农（Shannon）编码
将信源消息符号按其出现的概率大小依次排列
确定满足下列不等式的整数码长Ki。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
为了编成唯一可译码，计算第i个消息的累加概率
将累加概率Pi变换成二进制数。
取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。
香农（Shannon）编码方法
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
例 5.4 设信源共7个符号消息
香农（Shannon）编码方法
信源消息符号ai 符号概率p(ai) 累加概率Pi -log p(ai) 码字长度Ki 码字
a1 0.20 0 2.32 3 000
a2 0.19 0.2 2.39 3 001
a3 0.18 0.39 2.47 3 011
a4 0.17 0.57 2.56 3 100
a5 0.15 0.74 2.74 3 101
a6 0.10 0.89 3.32 4 1110
a7 0.01 0.99 6.64 7 1111110
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
码元/符号
比特/码元
香农（Shannon）编码方法
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.3 限失真信源编码定理
信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；
只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
*
5.3 限失真信源编码定理
限失真信源编码定理：
当R>R(D)，只要L足够长，一定存在一种编码方法，其译码失真小于或等于D＋，为任意小的正数。
反之，若R
=
+
+
+
=
–
–
–
–
=
–
å
i
K
i
Î
1
2
2
2
2
2
3
3
2
1
4
1
=
+
+
+
=
–
–
–
–
=
–
å
i
K
i
12
()
L
kK
YYYY
=
Y
LL
M
L
m
L
K
K
L
log
1
log
=
=
K
e
+
³
)
(
log
X
L
L
H
m
L
K
e
2
)
(
log
–
£
X
L
L
H
m
L
K
K
)
(
)
(
log
X
X
H
LH
m
K
L
L
=
>
)
(
X
L
H
K
<
)
(
X
L
H
K
=
2
2
)
(
e
s
L
P
e
X
£
}
)]
(
)
(
{[
)
(
2
2
X
x
X
H
I
E
i
-
=
s
)
(
2
X
s
2
e
d
e
s
£
2
2
)
(
L
X
d
e
s
2
2
)
(
X
³
L
2
2
)
(
e
s
L
P
e
X
£
K
H
L
)
(
X
=
h
K
0
,
)
(
)
(
>
+
=
e
e
h
X
X
L
L
H
H
1
log
)
(
®
m
L
K
H
L
L
X
ú
û
ù
ê
ë
é
ú
û
ù
ê
ë
é
04
.
0
05
.
0
06
.
0
07
.
0
1
.
0
1
.
0
18
.
0
4
.
0
8
7
6
5
4
3
2
1
a
a
a
a
a
a
a
a
P
X
＝
55
.
2
log
)
(
8
1
=
–
=
å
=
i
i
i
p
p
X
H
＝
h
K
¸
28
.
0
,
90
.
0
)
(
)
(
=
Þ
=
+
e
e
h
X
H
X
H
＝
2
2
8
1
2
2
)
(
82
.
7
)]
(
[
)
(log
)]
(
[
)
(
bit
X
H
p
p
x
I
D
X
i
i
i
i
=
–
=
=
å
=
s
6
10
－
£
d
8
7
6
2
2
2
10
10
8
.
9
10
28
.
0
82
.
7
)
(
»
´
=
´
=
³
–
d
e
s
X
L
()
ii
i
KpaK
=
å
1
log
)
(
log
)
(
+
<
£
m
X
H
K
m
X
H
e
+
<
£
)
(
)
(
X
X
L
L
H
K
H
K
X
H
m
L
K
X
H
L
L
L
)
(
1
log
)
(
1
1
-
=
-
=
-
=
h
g
符号
/
811
.
0
3
4
log
4
3
4
log
4
1
)
(
bit
X
H
=
+
=
ú
ú
û
ù
ê
ê
ë
é
=
ú
û
ù
ê
ë
é
4
1
4
3
2
1
a
a
P
X
811
.
0
)
(
=
=
K
X
H
h
1
,
0
2
1
®
®
a
a
K
32
27
2
2
=
=
K
K
16
27
3
16
1
3
16
3
2
16
3
1
16
9
2
=
´
´
´
´
=
＋
＋
＋
K
961
.
0
27
811
.
0
32
2
=
´
=
h
985
.
0
3
=
h
991
.
0
4
=
h
5
10
－
£
d
2
2
2
1
2
2
)
(
4715
.
0
)]
(
[
)
(log
)
(
bit
X
H
p
p
X
i
i
i
=
-
=
å
=
s
7
5
2
2
2
10
13
.
4
10
04
.
0
)
96
.
0
(
)
811
.
0
(
4715
.
0
´
´
·
³
＝
－
L
n
p
p
p
³
³
³
L
2
1
(
)
(
)
1
log
log
2
2
+
-
<
£
i
i
i
p
K
p
－
(
)
å
-
=
=
1
1
i
k
k
i
a
p
P
14
.
3
)
(
7
1
=
=
å
=
i
i
i
K
a
p
K
831
.
0
14
.
3
61
.
2
)
(
=
=
=
K
X
H
R
e
+
<
£
)
(
)
(
D
R
K
D
R
72
.
2
)
(
7
1
=
=
å
=
i
i
i
K
a
p
K
96
.
0
72
.
2
61
.
2
)
(
=
=
=
K
X
H
R
[
]
ú
û
ù
ê
ë
é
=
1
.
0
1
.
0
2
.
0
2
.
0
4
.
0
5
4
3
2
1
a
a
a
a
a
P
X
2
.
2
)
(
7
1
=
=
å
=
i
i
i
K
a
p
K
965
.
0
)
(
=
=
K
X
H
h
(
)
[
]
å
=
-
=
-
=
q
i
i
i
i
l
K
k
a
p
K
k
E
1
2
2
2
)
)(
(
s
36
.
1
2
1
=
l
s
16
.
0
2
2
=
l
s
ú
ú
ù
ê
ê
é
=
)
(
1
log
S
p
L
é
ù
î
í
ì
+
=
=
=
+
=
0
)
(
)
(
)
1
,
(
)
(
)
0
,
(
1
,
0
,
)
(
)
(
)
,
(
P
S
p
S
P
S
P
S
P
S
P
r
P
S
p
S
P
r
S
P
r
î
í
ì
=
+
=
r
r
p
S
A
Sr
A
P
S
A
S
C
Sr
C
)
(
)
(
)
(
)
(
)
(
î
í
ì
=
´
=
=
=
´
+
=
+
=
1
.
0
1
.
0
1
)
(
)
(
0
0
1
0
)
(
)
(
)
(
a
a
p
A
a
A
P
A
C
a
C
j
j
j
j
j
î
í
ì
=
´
=
=
=
´
+
=
+
=
001
.
0
01
.
0
1
.
0
)
(
)
(
01
.
0
1
.
0
1
.
0
0
)
(
)
(
)
(
b
b
p
a
A
ab
A
P
a
A
a
C
ab
C
ï
ï
î
ï
ï
í
ì
=
´
=
=
=
´
+
=
+
=
000001
.
0
001
.
0
001
.
0
)
(
)
(
010111
.
0
111
.
0
001
.
0
01
.
0
)
(
)
(
)
(
d
d
p
ab
A
abd
A
P
ab
A
ab
C
abd
C
ï
ï
î
ï
ï
í
ì
=
´
=
=
=
´
+
=
+
=
0000001
.
0
1
.
0
000001
.
0
)
(
)
(
010111
.
0
0
000001
.
0
010111
.
0
)
(
)
(
)
(
a
a
p
abd
A
abda
A
P
abd
A
abd
C
abda
C