FANG: DAC SPECTRUM OF BINARY SOURCES WITH EQUALLY-LIKELY SYMBOLS 3
1
1
0
0
0
0
1
1
0
1
...
...
...
...
Fig. 1. An example of the incomplete binary tree formed by the DAC
decoding. At each node, u is calculated according to (1). If (1 − p
α
) ≤
u<(1 − p)
α
, then both 0-branch and 1-branch are created; otherwise either
0-branch (if 0 ≤ u<(1 − p
α
)) or 1-branch (if (1 − p)
α
≤ u<1)is
created.
(upper, resp.) bound of the interval and code is the codeword
in the buffer. Let
u =
code − low
high − low
. (1)
Obviously 0 ≤ u<1. Depending on the value of u,the
decoder takes different actions:
• 0 ≤ u<(1 − p
α
): decide the current source symbol to
0 and create 0-branch;
• (1 − p
α
) ≤ u<(1 − p)
α
: cannot make a decision, so
create both 0-branch and 1-branch;
• (1 − p)
α
≤ u<1: decide the current source symbol to
1 and create 1-branch.
The decoder state of each branch is then updated:
• 0-branch: high is updated to low+(high−low)(1−p)
α
;
• 1-branch: low is updated to low+(high −low)(1−p
α
).
1) Behavior of Ideal DAC Decoder: The ideal DAC de-
coder retains all branches created during the decoding. After
the decoding is finished, each path will correspond to a
sequence of n binary symbols. Denote the j-thpathby
b
j
= {b
ji
}
n−1
i=0
,whereb
ji
is the i-th symbol of the j-
path. Given decoder SI y,thea posteriori probability of b
j
is Pr(b
j
|y)=
n−1
i=0
Pr(b
ji
|y
i
),wherePr(b
ji
|y
i
)= if
(b
ji
= y
i
) or (1 − ) otherwise. Finally, the path with the
maximum a posteriori probability is selected as the estimate
of x.
2) Behavior of Practical DAC Decoder: After each decod-
ing stage, the breadth-M decoder firstly sorts all paths accord-
ing to the partial a posteriori probability of each path. After
the i-th stage, each path corresponds to a sequence o f (i +1)
binary symbols. Denote the j-th path by b
i
j
= {b
ji
}
i
i
=0
.
Given decoder SI y, the partial a posteriori probability of
b
i
j
is Pr(b
i
j
|y)=
i
i
=0
Pr(b
ji
|y
i
). Then the breadth-M
decoder retains at most M branches with maximum partial
a posteriori probabilities by pruning other inferior branches.
Such operations are iterated. Finally, after the (n−1)-th stage,
from the M surviving paths, the path with the maximum
overall a posteriori probability is selected as the estimate of
x.
III. D
EFINITION OF DAC SPE CTRUM
Definition 1: DAC Spectrum Let X be the set of infinite-
length binary sequences. We encode each infinite-length bi-
nary sequence in X into a DAC code and then decode it by
the ideal DAC decoder to form an incomplete binary tree. The
stage-i DAC spectrum is defined as the probability density
function (PDF) of random variables u at all stage-i nodes in
all incomplete binary trees, where u is calculated by (1).
Denote the stage-i DAC spectrum by g
i
(u).Fromthe
properties of PDF, it is easy to get
1
0
g
i
(u)du =1 (2)
and
g
i
(u) ≥ 0, 0 ≤ u<1
g
i
(u)=0,u<0 or u ≥ 1
. (3)
For binary sources with equally-likely symbols, p
α
=(1−
p)
α
=2
−α
= q. Due to the symmetry,
g
i
(u)=g
i
(1 − u), 0 <u<1. (4)
Until now, all what we know about g
i
(u) are just (2), (3),
and (4). Below, we will make use of a recursive formulation
to deduce the explicit form of g
i
(u). Our first goal is to obtain
the explicit form of g
0
(u), the initial DAC spectrum at root
nodes. Then, we aim at expressing g
i+1
(u) as a function of
g
i
(u) in a recursive way.
The author has proposed in [1] the concept of DAC spectrum
along proper decoding branch (denoted by f(u)). In fact, f(u)
is equivalent to the initial DAC spectrum g
0
(u) because for
any infinite-length binary sequence x = {x
i
}
∞
i=0
, all of its
remaining sub-sequences x
i
= {x
i
}
∞
i
=i
just make up the set
of infinite-length binary sequences. Hence, f (u) will be used
instead of g
0
(u) below for simplicity.
IV. I
NITIAL DAC SPE CTRUM
Theorem 4.1: Initial DAC Spectrum The initial DAC
spectrum of infinite-length binary sources with equally-likely
symbols is constrained by [1]
2qf(u)=f
u
q
+ f
u − (1 − q)
q
. (5)
Proof: We divide X into two subsets X
0
and X
1
,where
X
0
(X
1
, resp.) contains all infinite-length binary sequences
beginning with symbol 0 (symbol 1, resp.) in X. Denote the
initial DAC spectrum of X
0
(X
1
,resp.)byf
0
(u) (f
1
(u),
resp.). It is obvious that
f(u)=Pr(x
0
=0)f
0
(u)+Pr(x
0
=1)f
1
(u)
=
f
0
(u)+f
1
(u)
2
. (6)
Now the problem is how to link f
0
(u) and f
1
(u) with f (u).
Let us begin with f
0
(u). We first discard the leading symbol 0
of each binary sequence in X
0
to obtain a new subset
ˆ
X
0
and
then map each binary sequence in
ˆ
X
0
onto interval [0,q). Thus
the initial spectrum of
ˆ
X
0
is just f
0
(u). Because both
ˆ
X
0
and
This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
剩余10页未读，继续阅读
weixin_38500090
- 粉丝: 4
- 资源: 964
我的内容管理
展开
最新资源
- C++标准程序库：权威指南
- Java解惑：奇数判断误区与改进方法
- C++编程必读：20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程：从入门到精通
- Spring3.0权威指南：JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略：从环境配置到索引创建
- 内存虚拟硬盘技术：提升电脑速度的秘密武器
- Java操作数据库：保存与显示图片到数据库及页面
- ISO14001：2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发：触发器与控制器重定向技术详解
- FPGA开发实战指南：创新设计与进阶技巧
- ShopExV4.8二次开发入门：解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
