约束系统编码入门：减少错误理论与设计

需积分: 10 134 浏览量更新于2024-07-21 收藏 3.55MB PDF 举报

《受限系统编码入门》是一篇由B. H. Marcus、R. M. Roth和P. H. Siegel在2001年编写的草案，主要针对数据记录系统和许多数据通信系统中常见的约束条件。在这些系统中，由于某些序列比其他序列更容易发生错误，为了减少错误发生的可能性，有必要对允许记录或传输的序列施加限制。作者在这篇文章中探讨了受限序列系统的理论以及在这种约束下进行编码设计的方法。首先，文章定义了受限系统的概念，即在一个系统中，只有满足特定规则的序列才能被接受。这可能涉及限制序列的长度、结构、或者遵循某种模式。在实际应用中，这些约束可能是由物理特性（如信号频率范围）、技术限制（如频谱效率）或者安全性考虑（如防止特定序列的恶意利用）所驱动。接着，编码设计成为关键环节。对于给定的用户输入序列，编码的目的是将其转换为受限的输出序列，以适应系统的约束。编码过程通常包括两个主要步骤：源编码（source coding）和信道编码（channel coding）。源编码是将原始数据压缩成满足约束的形式，而信道编码则是在编码过程中加入冗余信息，以便在传输过程中能够检测和纠正错误。文中可能讨论了各种编码技术，如霍夫曼编码（Huffman coding），这是一种基于频率的编码方法，用于高效地压缩高频率事件；或者是卷积码（convolutional codes），一种广泛应用于数字通信中的线性分组码，通过交织和循环移位来提高纠错能力。此外，还有可能涉及前向错误纠正（Forward Error Correction, FEC）算法，如Turbo编码、低密度 parity check（LDPC）码等。受限系统编码理论还涵盖了如何分析和评估编码性能，包括编码效率（如信息熵和冗余度）、编码复杂度（计算和存储需求）、以及编码的可靠性（误码率和纠错能力）。通过优化这些参数，编码设计者必须在实际应用的约束条件下找到一个平衡点，以提供最佳的性能。文章最后可能会讨论一些实际应用案例，例如在无线通信、图像和音频压缩、甚至是密码学中，受限编码是如何发挥重要作用的。此外，随着技术的进步，新的约束条件和编码策略也可能会被提出，比如在物联网（IoT）和5G通信中的序列管理和高效编码。《受限系统编码入门》是一本深入浅出的教材，旨在帮助读者理解和设计能够在受限环境中有效运作的编码方案，确保信息的准确性和可靠性。

CHAPTER 1. CHANNELS AND CONSTRAINTS

Figure 1.6. A

rate

nite-state encoder

accepts an arbitrary input blo ck of

user bits

and generates a co deword of length

|referred to as a

-codeword

|dep ending on the input

blo ck and the currentinternal state of the enco der. The sequences obtained by concatenating

the

-co dewords generated by the enco der must satisfy the constraint. There are of course

only nitely many states.

Enco der

Combinational

Logic

Enco der State











bits

Figure 1.6: Finite-state enco der schematic.

Example 1.1

Figure 1.7 depicts a rate 2 : 3 enco der for the (0



1)-RLL constrained

system Sie85a]. There are two states,

and

. Each state has exactly four outgoing edges.

Each edge has two lab els: a 2-bit input lab el and a 3-bit output lab el. To make a b etter

distinction b etween input and output lab els, we will refer to the former as input

tags

. Note

that at each state, the set of four outgoing edges carry all p ossible 2-bit input tags exactly

once.













011

' $

011

110

 

010

 

101

& %

111







101







111

Figure 1.7: Rate 2: 3 two-state enco der for (0



1)-RLL constrained system.

One encodes as follows. First, x an an initial state, saystate

. To enco de an arbitrary

2-bit input

, rst nd the unique outgoing edge

, with input tag

, from state

 the

enco ded 3-co deword is the output lab el of edge

. To enco de the next 2-bit input, execute

the same pro cedure starting from the terminal state of

. For instance, starting at state

the sequence

01 01 00 10 10 01 00 00

enco des to

011 111 011 110 101 111 011 011



CHAPTER 1. CHANNELS AND CONSTRAINTS

with corresp onding state sequence:

AB AAB B AAA :

The enco ded sequences do indeed satisfy the (0



1)-RLL constraint, i.e., one can never see

two consecutive 0's this follows from the observations: (1) one can never see two consecutive

0's on an edge output lab el, and (2) whenever an edge carries an output lab el that ends in

0, the following output lab els all b egin with 1.

The enco ders that we construct should be deco dable. One typ e of deco der that we con-

sider is a

state-dependent decoder

which accepts, as input, a

-co deword and generates a

length-

blo ck of user bits dep ending on the internal state, as well as nitely many up-

coming

-co dewords. Such a deco der will invert the enco der when applied to valid code

sequences, eectively retracing the state sequence followed by the enco der in generating the

co deword sequence. However, when the co de is used in the context of a noisy channel, the

state-dep endent deco der may run into a serious problem. The noise causes errors in the

detection of the co deword sequences, and the deco der must cop e with erroneously detected

sequences, including sequences that could not be generated by the enco der. It is generally

very imp ortant that the deco der limit the propagation of errors at the deco der output re-

sulting from such an error at the deco der input. Unfortunately, an error at the input to a

state-dep endent deco der can cause the deco der to lose trac

k of the enco der state sequence,

with no guarantee of recovery and with the p ossibilityof unb ounded error propagation.

Example 1.2

Consider the (admittedly articial) rate 1 : 1 enco der depicted in Fig-

ure 1.8.





















Figure 1.8: Enco der susceptible to unb ounded deco der error propagation

If we select state

as the initial state, then the sequence 000000



enco des to the

sequence

aaaaaa



. If a single channel error corrupts the rst

, then the state-

dep endent deco der will receive the sequence

baaaaa



and deco de to 111111



. So, a

single channel error at the b eginning may cause many deco ding errors.

The decoder therefore needs to have additional prop erties. Sp ecically,any symb ol error

at the deco der input should give rise to a limited numb er of bit errors at the decoder output.

sliding-block decoder

makes a decision on agiven received

-co deword on the basis of the

lo cal context of that co deword in the received sequence: the codeword itself, as well as a

CHAPTER 1. CHANNELS AND CONSTRAINTS

is why the co deword 011 deco des to 01 if it is followed by 101 or 111. Similarly, the edge

ending at state

can can b e followed only by edges whose output lab els are the co dewords

010, 011 or 110. This is why 011 deco des to 00 if it is followed by 010, 011 or 110.

Consider an application of the decoder in Table 1.1 to the following sequence of eight

3-co dewords

011 111 011 110 101 111 011 011 

this is the same sequence that was enco ded in Example 1.1. It can be easily veried that

the deco der will reco

ver correctly the rst seven resp ective 2-bit inputs

01 01 00 10 10 01 00



while the eighth 2-bit input can be either 00 or 01. Indeed, since the last 3-co deword is

011, the unique recovery of the eighth 2-bit input is p ossible only when the next (ninth)

3-co deword b ecomes available.

We p oint out that the inability to recover the eighth 2-bit input without additional

information is not a limitation of the decoder, but rather a consequence of the structure

of the enco der of Figure 1.7: the rst sev

en 2-bit inputs lead the enco der to state

, from

which there are two outgoing edges lab eled 011. So, unless more information is provided

(e.g., in the form of a ninth 3-co deword) there is no way to tell which edge generated the

eighth 3-co deword.

We emphasize that it is critical for both the enco der and deco der to have knowledge

of the correct framing of sequences into 2-bit inputs and 3-co dewords. For the former,

this is a pretty safe assumption since the input comes from the well-controlled computer

CPU. For the latter, this is not so safe. As discussed in Section 1.1 inaccurate clo cking

could cause the system to lose or gain a bit and therefore lose the framing into co dewords.

However, the

-constraint itself, as well as the co ding/synchronization scheme to b e discussed

in Section

1.5.2, help to ensure that the deco der has access to the correct framing.

In the literature, the term \co de rate" can refer to either the pair of numb ers,

,orthe

ratio,

p=q

, between these numb ers. This is a genuine ambiguity since

is more sp ecic

than

p=q

. For instance, a rate 2:3 enco der is literally dierent from a rate 4:6 enco der.

However, the two uses of the term can usually be distinguished from context. In this text

we continue tradition by using the term \co de rate" to refer to b oth

and

p=q

Shannon

proved Sha48] that the rate

p=q

of a constrained enco der cannot exceed a

quantity, now referred to as the Shannon capacity, that dep ends only up on the constraint

(see Chapter 3). He also gave a non-constructive pro of of the existence of co des at rates less

than, but arbitrarily close to, the capacity. Therefore, as well as the issues of deco dability

mentioned ab ove, any enco ding/deco ding scheme will be measured by the proximity of its

rate,

p=q

,totheShannon capacity.

剩余292页未读，继续阅读

haiquancheng

粉丝: 3
资源: 12

约束系统编码入门：减少错误理论与设计

SOLUTIONS MANUAL FOR AN INTRODUCTION TO CRYPTOGRPHY WITH CODING

Algorithmic introduction to coding theory

Network Coding An Introduction

An Introduction to Data Science

An Introduction to the Multi-User MIMO Downlink

Introduction To Digital Audio Coding And Standards

Introduction to High Efficiency Video Coding

An Introduction to Programming and Numerical Methods in MATLAB.pdf

Make Your Own Algorithmic Art: A Gentle Introduction to Creative Coding

Locality-constrained Linear Coding for Image Classiﬁcation

最新资源