Communications for Control in Cyber Physical Systems

【有计划得了解一下法国的Turbo中国的 polar和美国的LDTC】

SEQUENTIAL ESTIMATION

For the linear dynamics in Eq. (5.4), system state estimation can be considered as a lossy source coding problem, since the sensor encodes the observations and the decoder output always has errors except in trivial cases. The lossy source coding is traditionally studied using rate-distortion theory [33], as a branch of information theory, which discusses the minimum communication requirement to satisfy the requirement on the distortion at the decoder output.

对于等式中的线性动力学。 (5.4),系统状态估计可以被认为是有损源编码问题,因为传感器对观测值进行编码,并且解码器的输出总是有误差,除非是在平凡的情况下。传统上使用速率失真理论[33]作为信息理论的一个分支来研究有损源编码,该理论讨论了满足解码器输出失真要求的最低通信要求。

However, the information-theoretic argument is based on the assumption of infinite codeword length and thus infinite delays, which is reasonable for traditional data communications (e.g., one packet encoded as a codeword may have thousands of bits). Obviously such arguments are not suitable for CPSs, since the encoding procedure must have a limited delay. Hence in contrast to the block structure of traditional data communications, the encoding procedure in a CPS should have a sequential structure, as illustrated in Fig. 5.13. Before we study sequential rate distortion, we provide a review of traditional ratedistortion theory. When the true information symbol is x while the recovered one

然而,信息理论论证是基于无限码字长度以及无限延迟的假设,这对于传统的数据通信是合理的(例如,被编码为码字的一个分组可以具有数千个比特)。显然,此类参数不适用于CPS,因为编码过程必须具有有限的延迟。因此,与传统数据通信的块结构相反,CPS中的编码过程应具有顺序结构,如图5.13所示。在研究顺序速率失真之前,我们将回顾传统的评级理论。当真实信息符号为x时,恢复的符号为y,则失真为D(x,y),率失真函数定义如下:

For a certain information source generating symbols {X(t)}, the rate-distortion function is defined as

对于某些生成符号{X(t)}的信息源,率失真函数定义为

where QY|X is the conditional probability of generating the recovered symbol Y given the true information symbol X, DQ is the distortion incurred by the conditional distribution QY|X, and I is mutual information. Intuitively, the rate-distortion function means the minimum average number of bits needed to achieve a distortion less than or equal to D. Meanwhile, the ratedistortion function can also determine whether a communication channel with a certain capacity can support the transmission of an information source with a given distortion bound. Roughly speaking, when transmitting the information of a GaussMarkov process through a communication channel having capacity C, distortion D can be achieved if R(D) < C, while it cannot be achieved if R(D) > C. This dichotomy is illustrated in Fig. 5.14. Similarly to the traditional definition of rate-distortion function with infinite delay, Ref. [14] defined the sequential rate-distortion function as follows:

其中QY | X是在给定真实信息符号X的情况下生成恢复符号Y的条件概率,DQ是由条件分布QY | X引起的失真,I是互信息。 直觉上,速率失真函数是指,实现小于或等于D的失真所需的最小平均bit数。同时,率失真功能还可以确定具有一定容量的通信信道是否可以支持 具有给定的失真范围的 信息源的传输 。 粗略地讲,当通过具有容量C的通信信道传输高斯马氏过程的信息时,如果R(D)< C,则不能实现失真D。 图5.14。 与具有无限延迟的速率失真函数的传统定义相似,参考文献。 [14]定义顺序速率失真函数如下:

We notice that the sequential rate-distortion function has the following features:
• The necessary rate may be dependent on the time T.
• Only the causal information is considered in the mutual information, which is
due to the requirement of sequential decoding.
• The expected distortion is no larger than D for each time slot, instead of beingaveraged over all time slots.
The following theorem shows the application of the sequential rate-distortionfunction in the lossy transmission of information sources [14]. Note that a sufficientcondition is much more difficult to find.
Theorem 9. Consider a memoryless communication channel with channel capacity C. A necessary condition for achieving the distortion D causally is RsT (D) ≤ Cfor all T.

我们注意到顺序速率失真功能具有以下功能:
•必要的速率可能取决于时间T。
•互为信息中仅考虑因果信息,即由于需要顺序解码。
•每个时隙的预期失真不大于D,而不是在所有时隙中平均。
下面的定理说明了顺序速率失真函数在信息源有损传输中的应用[14]。 注意,要找到足够的条件要困难得多。
定理9.考虑信道容量为C的无记忆通信信道。对于所有T,实现失真D的必要条件是RsT(D)≤C。

Gauss-Markov source

Since the sequential rate-distortion function provides a lower bound for the channel capacity of the communication channel, it is important to calculate the sequential rate-distortion function for various information sources for the purpose of online system state estimation. We follow the argument in Ref. [14] to discuss the sequential rate-distortion function for a d-dimensional Gauss-Markov source where

由于顺序速率失真函数为通信信道的信道容量提供了一个下限,因此出于在线系统状态估计的目的,计算各种信息源的顺序速率失真函数很重要。 我们遵循参考文献中的论点。 [14]讨论了d维高斯-马尔可夫源的连续速率失真函数,其中

We assume a Gaussian communication channel with dimension d. The following lemma shows the necessary property for the infimizing channel in Eq. (5.68) in the definition of a sequential rate-distortion function: Lemma 3. The infimizing channel in the Gauss-Markov information source in Eq. (5.70), namely P(dY(t)|x(0 : t − 1), y(0 : t − 1)), is a Gaussian channel of the form P(dY(t)|x(t), y(0 : t − 1)).

我们假设维数为d的高斯通信信道。 以下引理显示了等式中的弱化通道的必要属性。 (5.68)在顺序速率失真函数的定义中:引理3。等式中高斯-马可夫信息源中的弱化通道。 (5.70),即P(dY(t)| x(0:t-1),y(0:t-1))是形式为P(dY(t)| x(t)的高斯通道, y(0:t − 1))。

Rate distortion

In the context of causal coding, the rate-distortion function rc(D) is defined to be the minimum average transmission rate such that the average distortion is no larger than D. It is shown in Ref. [150] that rc(D) is determined as follows:

在因果编码的上下文中,将速率失真函数rc(D)定义为最小平均传输速率,以使平均失真不大于D。 [150] rc(D)的确定如下:

where d(f) denotes the average distortion caused by the coder f . An interesting conclusion in Theorem 3 of Ref. [150] is that the causal rate-distortion functions in the above coder schemes are all the same when the information source is memoryless. However, it is still an open problem to compare the rate-distortion functions when the information source has memory

其中d(f)表示由编码器f引起的平均失真。 参考文献定理3中一个有趣的结论。 [150]是当信息源是无记忆的时,上述编码器方案中的因果率失真函数都相同。 但是,当信息源具有存储器时,比较速率失真函数仍然是一个未解决的问题。

SOURCE CODING IN A CPS: POINT-TO-POINT CASE

Source coding encodes the original information (either continuous or discrete valued) into discrete information bits. The main purpose is to reduce redundancy and thus transmit fewer bits (thus using fewer communication resources). In many existing CPSs, the measurements (e.g., the frequency and phase measurements at phasor measurement units (PMUs) in smart grids) are quantized with certain precisions and then sent to the controller. However, such a straightforward scheme may waste communication resources for the following reasons:

源编码将原始信息(连续值或离散值)编码为离散信息位。 主要目的是减少冗余并因此发送更少的比特(从而使用更少的通信资源)。 在许多现有的CPS中,测量值(例如,智能电网中的相量测量单元(PMU)的频率和相位测量值)以一定的精度进行量化,然后发送到控制器。 但是,由于以下原因,这种简单的方案可能会浪费通信资源:

  • • Ignoring temporal redundancy: The measurements at different times are usually correlated. For example, in power grids, the frequency and phase measurements are continuous in time and do not change very rapidly. Hence successive measurements are similar to each other, and it is not necessary to fully quantize each measurement in an independent manner. A possibly more efficient approach is to quantize increments in the frequency and phase.
  • •忽略时间冗余:通常将不同时间的测量结果关联起来。 例如,在电网中,频率和相位测量在时间上是连续的,并且变化不是很快。 因此,连续的测量彼此相似,因此不必以独立的方式完全量化每个测量。 一种可能更有效的方法是量化频率和相位的增量。
  • • Ignoring spatial redundancy: When there are multiple sensors, the measurements at different sensors are usually correlated, unless the sensors happen to measure orthogonal subspaces. The redundancies among different sensors can be fully utilized to decrease the source coding rate, even though there are no communications among the sensors (and thus no explicit coordination among them).
  • •忽略空间冗余:当有多个传感器时,除非传感器碰巧测量正交子空间,否则通常会关联不同传感器的测量结果。 即使传感器之间没有通信(因此它们之间没有明确的协调),也可以充分利用不同传感器之间的冗余来降低源编码率。

In this section we assume a single sensor and consider only temporal redundancy. Spatial redundancy will be considered in the next section. In traditional communication systems, the temporal redundancy can be compressed by carrying out joint source coding for all the source information symbols. However, such a source coding scheme requires a long latency since the coding needs to be carried out until all the source information symbols have been gathered. A long communication latency is intolerable for real-time feedback control in a CPS. Hence it is of key importance to study real-time source coding, in which the source information symbols are encoded in a sequential manner.

在本节中,我们假设使用单个传感器,并且仅考虑时间冗余。 下一部分将考虑空间冗余。 在传统的通信系统中,可以通过对所有源信息符号执行联合源编码来压缩时间冗余。 但是,这种源编码方案需要较长的等待时间,因为需要进行编码直到所有源信息符号都被收集为止。 对于CPS中的实时反馈控制,漫长的通信延迟是无法忍受的。 因此,研究实时源编码至关重要,在实时源编码中,源信息符号以顺序方式进行编码。

SYSTEM MODEL

Obviously, the output of the decoder is dependent only on the received bits and is thus nonanticipating.

显然,解码器的输出仅取决于接收的位,并且 因此是意料之外的。

STRUCTURE OF CAUSAL CODERS

Sliding block causal coders In this case the output of a decoder at time t is given by 在这种情况下,解码器在时间t的输出为

If the coder has finite memory, then we have where M is the memory length.

Block causal coders In such coders, the information is encoded and decoded in a block manner, namely

where k is the index of the block (or codeword). Obviously, such a coding scheme will cause an average delay N/2.

Block stationary coders Block stationary coders can be considered as a combination of sliding block causal coders and block causal coders. The output is given by

where the decoder output is in blocks and the decoding procedure uses all the previous received bits.

Finite-state causal coders A challenge of sliding block causal coders and block stationary coders is that infinite memory is needed to store all the previously received bits. To alleviate this problem while not discarding the history, a state S can be defined for the coders, such that the decoder output is a function of the state and the newest information symbol, namely

滑动块因果编码器和块固定编码器的挑战是需要无限的存储器来存储所有先前接收的位。 为了缓解此问题,同时又不放弃历史记录,可以为编码器定义状态S,以使解码器输出取决于状态和最新信息符号,即

and the system state S evolves in the following law:

SHANNON ENTROPY

Information and communications are triggered by uncertainties of information source (which can be represented by a random variable or random process). When the random variable is realized and has a deterministic value, the more uncertain the random variable is, the more information we can obtain. For a random variable X with finite alphabet XX and probability distribution P, its Shannon entropy is defined as

信息源的不确定性(可由随机变量或随机过程表示)触发信息和通信。 当随机变量实现并具有确定性值时,随机变量的不确定性越大,我们可以获得的信息就越多。 对于具有有限字母XX和概率分布P的随机变量X,其香农熵定义为

where the unit is bit (or nat) when the logarithm base is 2 (or e). In the special case of uniform distribution, the entropy of X is given by log |X |, where |X | is the cardinality of X . For example, if X has eight possible values, then we obtain 3 bits when X is determined. Similarly, for two random variables X and Y, we can also define the joint information as

当对数底数为2(或e)时,单位为bit(或nat)。 在均匀分布的特殊情况下,X的熵由log | XX |给出,其中| XX | 是XX的基数。 例如,如果X具有八个可能的值,那么当确定X时,我们将获得3位。 类似地,对于两个随机变量X和Y,我们还可以将联合信息定义为

MUTUAL INFORMATION

For two random variables X and Y, the mutual information is to measure the amount of randomness they share. It is defined as

对于两个随机变量X和Y,相互信息用于度量它们共享的随机性量。 定义为

I(X; Y) = H(X) − H(X|Y) = H(Y) − H(Y|X).

When I(X; Y) = H(X), X and Y completely determine each other; on the other hand, if I(X; Y) = 0, X and Y are mutually independent. As we will see, the mutual information is of key importance in deriving the capacity of communication channels.

当I(X; Y)= H(X)时,X和Y完全能相互确定。 另一方面,如果I(X; Y)= 0,则X和Y相互独立。 就像我们将看到的那样,相互信息对于推导通信渠道的容量至关重要。

COMMUNICATION CHANNELS

Below we introduce some typical communication channels and their corresponding characteristics:

  • • Wireless channels: The information is carried by electromagnetic waves in the open space. There are many typical wireless communication systems such as 4G cellular systems and WiFi (IEEE 802.11) systems, which enable mobile communications. However, wireless channels are often unreliable and have relatively small channel capacities.
  • •无线通道:信息是由开放空间中的电磁波传送的。 有许多典型的无线通信系统,例如4G蜂窝系统和WiFi(IEEE 802.11)系统,可实现移动通信。 但是,无线信道通常不可靠并且具有相对较小的信道容量。
  • • Optical fibers: The information can also be sent through optical fibers in wired communication networks. This communication channel is highly reliable and can support very high communication speeds. It is often used as the backbone network in a large area communication network such as the Internet.
  • •光纤:信息也可以通过有线通信网络中的光纤发送。 该通信通道高度可靠,可以支持很高的通信速度。 它通常用作诸如Internet之类的大范围通信网络中的骨干网络。
  • • Underwater channels: Underwater acoustic waves can convey information with very low reliability and very low communication rates, which can be used in underwater communications such as submarine or underwater sensor communications.
  • •水下通道:水下声波可以以非常低的可靠性和非常低的通信速率传输信息,可用于水下通信(例如,潜艇或水下传感器通信)中。

A communication channel can be modeled using conditional probabilities. Given an input x, the channel output y is random due to random noise, and is characterized by the corresponding conditional probability P(y|x). Several typical models of communication channels are given below, as illustrated in Fig. 2.2:

可以使用条件概率对通信通道进行建模。 在给定输入x的情况下,通道输出y由于随机噪声而具有随机性,并以相应的条件概率P(y | x)为特征。 下面给出了几种典型的通信信道模型,如图2.2所示:

  • • Binary symmetric channel: Both the input and output are binary with alphabet {0, 1}. The input is swapped at the output with probability 1 − p. Such a model can be used to describe the errors in demodulation and decoding, where 1 − p is the error probability of each information bit.
  • •二进制对称通道:输入和输出均为二进制,字母为{0,1}。 输入在输出处以概率1- p交换。 这样的模型可用于描述解调和解码中的错误,其中1-p是每个信息比特的错误概率。
  • • Erasure channel: The input is binary. A new element , which denotes the loss of information, is added to the output, besides bits 0 and 1. Such a model can depict communication systems with possible packet losses, such as the Internet.
  • •擦除通道:输入为二进制。 除位0和1之外,还将一个表示信息丢失的新元素添加到输出中。这种模型可以描述具有可能的数据包丢失的通信系统,例如Internet。
  • • Gaussian channel: Both the input and output of the channel are real numbers. The output is a superposition of the input and Gaussian noise, i.e., y(t) = x(t) + n(t),
  • •高斯通道:通道的输入和输出均为实数。 输出是输入和高斯噪声的叠加,即y(t)= x(t)+ n(t),

As will be seen, the SNR is of key importance in determining the performance of Gaussian channels.

可以看出,SNR对确定高斯信道的性能至关重要。

  • • Gaussian band-limited channel: This channel is continuous in time. The additive noise has power spectral density N0 and the signal is allowed to transmit within a frequency band with bandwidth W.
  • 高斯带限信道:该信道在时间上是连续的。 附加噪声的功率谱密度为N0,并且允许信号在带宽为W的频带内传输。
  • • Multiple access channel: When there are multiple (say K) transmitters and a single receiver, the transmitted signals will have an effect on each other. For the discrete case, the channel is characterized by the conditional probability given
  • 多路访问信道:当有多个(例如K个)发射器和一个接收器时,所发射的信号将相互影响。 对于离散情况,信道的特征在于给定的条件概率

An important special case is the Gaussian multiple access channel, in which the received signal is given by 一个重要的特殊情况是高斯多路访问信道,其中接收信号由n是高斯噪音

CHANNEL CAPACITY

In his groundbreaking paper [32], Shannon proposed the concept of channel capacity C (bits/channel use) for communication channels; i.e., if the transmission rate R (also bits/channel use) is less than C, then there exists an encoding and decoding scheme to make the transmission error arbitrarily small; otherwise, the data cannot be reliably transmitted. For the simplest case of discrete memoryless channels, the channel capacity is given by

在其开创性的论文[32]中,Shannon提出了通信信道的信道容量C(位/信道使用)的概念。 即,如果传输速率R(也使用比特/信道)小于C,则存在一种编码和解码方案,以使传输误差任意小; 否则,数据将无法可靠传输。 对于离散无记忆通道的最简单情况,通道容量由下式给出:

  • • The binary symmetric channel has a channel capacity of 1 − H(p), where H(p) = −p log p − (1 − p)log(1 − p) is the Shannon entropy of a binary distribution with probabilities p and 1 − p.
  • • The erasure channel has a channel capacity p, where p is the probability that the transmitted bit is not erased.
  • • The Gaussian channel has the following channel capacity:
  • •二进制对称信道的信道容量为1-H(p),其中H(p)= -p log p-(1-p)log(1-p)是概率为p的二进制分布的Shannon熵 和1-p。
  • •擦除通道的通道容量为p,其中p是未擦除所传输位的概率。
  •   •高斯通道具有以下通道容量:

where Ps is the maximum average power, if the constraint is the average power (instead of the peak power).

• The band-limited Gaussian channel has the following channel capacity:

if the constraint is on the average power.

• Multiple access channel: When there are K transmitters, the communication capability is described by the capacity region Ω, within which each point (R1, … , RK) is achievable. For the Gaussian multiple access channel, we have

多路访问信道:当有K个发射机时,通信能力由容量范围Ω来描述,在该范围内可以实现每个点(R1,…,RK)。 对于高斯多路访问信道,我们有

Although the concept of channel capacity has been widely used in the practical design of communication systems, the following points need to be noted in the context of communications in a CPS.

尽管信道容量的概念已在通信系统的实际设计中得到广泛使用,但在CPS中进行通信时需要注意以下几点。

• The channel capacity defined in traditional information theory is based on asymptotic analysis and infinite codeword length. However, in the context of CPS, due to the requirement of real-time for controlling the dynamics, the infinite codeword length, which also implies infinite communication delay, cannot be tolerated.

传统信息理论中定义的信道容量基于渐近分析和无限码字长度。 但是,在CPS的情况下,由于需要实时控制动态特性,因此不能容忍无限的码字长度,这也意味着无限的通信延迟。

• The achievability of channel capacity is usually based on the argument of random coding, which is of theoretical importance but is not practical. Although for simple binary channels the low-density parity-check (LDPC) codes have almost attained the channel capacity, the practical capacity of coding schemes has not been obtained for many typical channel models.

•信道容量的可实现性通常基于随机编码的论点,这在理论上很重要,但不切实际。 尽管对于简单的二进制信道,低密度奇偶校验(LDPC)码几乎达到了信道容量,但是对于许多典型的信道模型,尚未获得编码方案的实际容量。

SOURCE CODING

Source coding means converting from the original information, which could be either discrete or continuous, to a series of information bits. It can be categorized into lossless source coding, in which no information is lost during the source coding, and lossy source coding, in which a portion of the information is lost. For simplicity, we assume that the information symbols are discrete-time and i.i.d.

源编码意味着将原始信息(可以是离散的或连续的)转换为一系列信息位。 可以将其分类为无损源编码,在无损源编码中,没有在源编码期间丢失任何信息,在无损源编码中,有一部分信息丢失了。 为简单起见,我们假设信息符号为离散时间和i.d.

LOSSLESS SOURCE CODING

The information source of lossless source coding, which is represented by a random variable X, must be finite. Denote by X = {x1, … , xn} the alphabet of the information source symbols. It is assumed that the distribution is {P(X = xj)}j. One simple approach is to use log2 n bits to represent these n symbols. However, we can do better and use variable length code, in which the information symbols may be represented by different numbers of bits. To achieve the lower average code length, we should assign fewer bits to more frequent symbols. It has been shown that the minimum average number of bits is given by H(P) (i.e., the entropy of X) and can be achieved by properly assigning the bits to the symbols with known probabilities.

由随机变量X表示的无损源编码的信息源必须是有限的。 X = {x1,…,xn}表示信息源符号的字母。 假设分布为{P(X = xj)} j。 一种简单的方法是使用log2 n位来表示这n个符号。 但是,我们可以做得更好,并使用可变长度代码,其中信息符号可以由不同数量的比特表示。 为了获得较低的平均代码长度,我们应该将更少的位分配给更频繁的符号。 已经表明,最小的平均比特数由H(P)(即,X的熵)给出,并且可以通过将比特适当地分配给具有已知概率的符号来实现。

The above discussion assumes known distributions of the information symbols. In practice, it is possible that the distribution is unknown and we only have a sequence of bits. In the situation of unknown statistics, a technique of universal source coding, such as the Lempel-Ziv coding scheme, can be applied. A surprising conclusion is that, even though the statistical information is lacking, the universal coding can still achieve the optimal compression rate asymptotically (as the length of sequence tends to infinity), given that the information source is stationary and ergodic.

以上讨论假设信息符号的已知分布。 实际上,分布是未知的,而我们只有一个比特序列。 在统计数据未知的情况下,可以应用通用源编码技术,例如Lempel-Ziv编码方案。 一个令人惊讶的结论是,即使缺少统计信息,考虑到信息源是固定且遍历的,通用编码仍可以渐近地实现最佳压缩率(因为序列的长度趋于无穷大)。

LOSSY SOURCE CODING

When the information source is continuous in value, it is impossible to encode the source information symbols using finitely many bits. Hence some information has to be lost when digital communications are used. We say that the source coding is lossy in this situation. Note that we can also apply lossy source coding for discrete information sources, if some information loss is tolerable.

当信息源的值是连续的时,不可能使用有限的许多位来编码源信息符号。 因此,当使用数字通信时,某些信息必须丢失。 我们说源编码在这种情况下是有损的。 注意,如果某些信息丢失是可以容忍的,我们也可以对有离散信息源应用有损源编码。

Theoretically, lossy source coding can be studied using rate-distortion theory [33]. First a distortion function is defined as d(X, Xˆ), where X is the information symbol and Xˆ is the recovered one. For example, when X is real valued, the distortion can be defined as the mean square error; i.e., d(X, Xˆ) = E[|X − Xˆ| 2]. Then a ratedistortion function R(D) is defined for each given average distortion D, which means the minimum source coding rate ensuring that the average distortion is no larger than D. It is well known that R(D) can be obtained from the optimization of mutual information between X and Xˆ. In practice, lossy source coding is carried out by a quantizer.

从理论上讲,可以使用速率失真理论研究有损源编码[33]。 首先,将失真函数定义为d(X,Xˆ),其中X是信息符号,Xˆ是恢复的符号。 例如,当X为实数时,可以将失真定义为均方误差。 即d(X,Xˆ)= E [| X − Xˆ | 2]。 然后,为每个给定的平均失真D定义一个额定失真函数R(D),这意味着最小源编码速率,确保平均失真不大于D。众所周知,可以从优化中获得R(D) X和Xˆ之间的相互信息。 实际上,有损源编码是由量化器执行的。

Essentially a quantizer divides the scope of the information source symbol X into many regions, each of which corresponds to a bit string. Fig. 2.3 shows a simple scalar quantizer, in which the range of X is the interval [0, 1] and it is divided into four intervals. When X falls in one of the intervals, the quantizer outputs the corresponding two bits. When X is a vector, a vector quantizer is needed, which is much more complicated. A powerful design algorithm for vector quantizers is Lloyd’s algorithm [34].

本质上,量化器将信息源符号X的范围划分为许多区域,每个区域对应于一个位串。 图2.3显示了一个简单的标量量化器,其中X的范围是间隔[0,1],并将其分为四个间隔。 当X落入间隔之一时,量化器输出相应的两位。 当X是向量时,需要向量量化器,这要复杂得多。 Lloyd算法[34]是矢量量化器的强大设计算法。

MODULATION AND CODING

When receiving a series of information bits, the transmitter will convert them to physical symbols ready for transmission. Usually two steps are needed for this conversion. First the information bits are encoded by adding redundancies in order to combat the communication channel unreliability and the potential errors arising from this. Then the coded bits are converted to physical symbols that are ready to be passed to the hardware for transmission.

当接收到一系列信息比特时,发送器会将它们转换为准备传输的物理符号。 通常,此转换需要两个步骤。 首先,通过添加冗余来对信息比特进行编码,以应对通信信道的不可靠性以及由此引起的潜在错误。 然后,将编码后的位转换为物理符号,准备将其传递给硬件进行传输。

CHANNEL CODING

There are two types of channel coding used to protect the transmission reliability from the channel uncertainty. In error detection coding, mistakes during the transmission may be detected. In error correction coding, the errors may be corrected without retransmitting the message.

有两种类型的信道编码用于保护传输可靠性免受信道不确定性的影响。 在错误检测编码中,可以检测到传输期间的错误。 在纠错编码中,可以在不重新发送消息的情况下纠正错误。

Error detection coding

In error detection coding schemes, typical errors during the transmission can be detected. Then the received codeword may be discarded and the failure of the transmission is announced; or the receiver will send back a request to the transmitter for retransmission. The simplest scheme of error detection is the parity check bit, namely the sum of the information bits is appended to the codeword. For example, when the original information bits are 1100111, the transmitted bit sequence is 11001111, where the last bit 1 is the parity check bit. If an error occurs in one of the information bits and the receiver receives 11001110, then the error can be detected since the parity check bit is unequal to the sum of the information bits. Although it is also possible that the parity check bit, or two information bits, is wrong, the corresponding probability is much smaller.

在错误检测编码方案中,可以检测到传输期间的典型错误。 然后,可以丢弃接收到的码字,并宣布传输失败; 否则接收方将向发送方发送请求以进行重传。 错误检测的最简单方案是奇偶校验位,即信息位的总和被附加到码字上。 例如,当原始信息位是1100111时,发送的位序列是11001111,其中最后一位是奇偶校验位。 如果在信息位之一中发生错误,并且接收器接收到11001110,则可以检测到该错误,因为奇偶校验位不等于信息位之和。 尽管奇偶校验位或两个信息位也可能是错误的,但是相应的概率要小得多。

Error correction coding

In the error correction coding scheme, typical errors in transmission can be corrected at the receiver without retransmission. The capability of error correction is assured by adding redundancies to the information bits. Take the simplest repetition code, for example. When we transmit bit 1, we can transmit it three times, thus sending out bit sequence 111.

在纠错编码方案中,可以在接收机处纠正传输中的典型错误而无需重发。 通过向信息位添加冗余来确保纠错能力。 以最简单的重复代码为例。 当我们发送位1时,我们可以发送3次,从而发出位序列111。

The decoder uses the majority rule; i.e., the decision is the most frequent bit in the received sequence. Hence if there is one transmission error and the decoder receives bits 011, the decoder can claim that the information bit is actually 1 and thus correct the error. The transmission rate, usually denoted by R, is defined as the ratio between the number of information bits and the number of coded bits. The above example of repetition code has a transmission rate 1/3. The smaller R is, the more redundancies are added and the more reliable the transmission is; however, a smaller R also uses more communication bandwidth since the transmitter needs to send out more coded bits in the same time. A tradeoff is needed between the reliability and resource consumption.

解码器使用多数规则; 即,该决定是所接收序列中最频繁的比特。 因此,如果存在一个传输错误,并且解码器接收到位011,则解码器可以声明信息位实际上为1,从而纠正该错误。 传输速率(通常用R表示)定义为信息位数和编码位数之间的比率。 上面的重复码示例的传输速率为1/3。 R越小,添加的冗余越多,传输越可靠。 但是,较小的R也会占用更多的通信带宽,因为发送器需要同时发送更多的编码位。 需要在可靠性和资源消耗之间进行权衡。

A typical error correction coding scheme used in practice is the linear block code, in which the coded bits c are given by c = bG, (2.14) where b represents the information bits (as a row vector) and G is called the generation matrix. The receiver receives a senseword s = c + e, where e is the error vector. The decoder applies a matrix H, which satisfies GTH = 0, to calculate d = sH = eH, which is called the syndrome. The error vector e can be found by looking up a table indexed by the syndrome.

在实践中使用的典型纠错编码方案是线性块码,其中编码位c由c = bG给出,(2.14)其中b代表信息位(作为行向量),G称为生成矩阵 。 接收器接收到一个感测词s = c + e,其中e是误差向量。 解码器应用满足GTH = 0的矩阵H来计算d = sH = eH,这被称为校正子。 可以通过查找由校正子索引的表来找到误差向量e。

A more powerful error correction code is the convolutional code, which does not have a fixed codeword length and is thus different from the linear block code. In the convolutional code, memory is introduced by streaming the input information bits through registers. Take the structure in Fig. 2.4, for example. There are two registers; thus the memory length is 2. For each input information bit b(t), the two coded bits, denoted by c1(t) and c2(t), are generated by b(t) and the previous two information bits b(t − 1) and b(t − 2), which are given by

卷积码是功能更强大的纠错码,它没有固定的码字长度,因此与线性分组码不同。 在卷积码中,通过将输入信息位通过寄存器流式传输来引入存储器。 以图2.4中的结构为例。 有两个寄存器; 因此,存储长度为2。对于每个输入信息位b(t),由b(t)生成由c1(t)和c2(t)表示的两个编码位,以及前两个信息位b(t − 1)和b(t − 2),分别为

Then the two registers are occupied by b(t −1) and b(t). Since one input information bit triggers the generation of two coded bits, the transmission rate is 1 2 . By changing the number of simultaneous output coded bits and the number of branches of the input bits, we can achieve any rational number for transmission rates. As we will see in later chapters, the structure of the convolutional code is actually similar to that of linear dynamical systems, thus facilitating the proposed turbo channel decoding and system state estimation in CPSs. A breakthrough in the area of error correction codes is the turbo code, which was proposed by Berrou et al. in 1993 [35] and achieves transmission rates very close to the Shannon limit of channel capacity (Fig. 2.5). For simplicity, we use the original form of turbo codes given in Ref. [35].

然后,两个寄存器分别被b(t -1)和b(t)占用。 由于一个输入信息位触发生成两个编码位,因此传输速率为1 2。 通过改变同时输出编码位的数量和输入位的分支数量,我们可以获得传输速率的任何合理数量。 正如我们将在后面的章节中看到的那样,卷积码的结构实际上与线性动态系统的结构相似,从而简化了CPS中建议的Turbo信道解码和系统状态估计。 纠错码领域的突破是Turbo码,它是Berrou等人提出的。 在1993年[35]达到了非常接近香农信道容量极限的传输速率(图2.5)。 为简单起见,我们使用Ref.3中给出的原始形式的Turbo代码。 [35]。

The encoder essentially uses a parallel convolutional code. Two convolutional encoders are used. The raw information bits, and a randomly permeated version of the bits (carried out by an interleaver), are fed into the two convolutional codes. Then the output of the turbo encoder consists of the original information bits and the output bits of the two convolutional encoders. The key novelty in the turbo code is in its decoder, which is illustrated in Fig. 2.6. The received encoded bits at the decoder consist of three parts: m (the original information bits with possible errors), X1 (the output of convolutional encoder 1), and X2 (the output of convolutional encoder 2). m and X1 are fed into a standard decoder, which generates the soft decoding output (namely the probability distribution of each bit being 0 or 1), instead of hard decisions.

编码器本质上使用并行卷积码。 使用了两个卷积编码器。 原始信息比特和这些比特的随机渗透版本(由交织器执行)被馈送到两个卷积码中。 然后,turbo编码器的输出由原始信息位和两个卷积编码器的输出位组成。 Turbo代码中的关键新颖之处在于其解码器,如图2.6所示。 在解码器处接收到的编码位包括三部分:m(可能有错误的原始信息位),X1(卷积编码器1的输出)和X2(卷积编码器2的输出)。 m和X1馈入标准解码器,该解码器生成软解码输出(即每个位的概率分布为0或1),而不是硬判决。

The soft output is fed into decoder 2 as prior information. Decoder 2 combines m, X2 and the prior information from decoder 1, and also generates soft outputs. Then the outputs of decoder 2 are fed into decoder 1 as prior information. Such a procedure is repeated iteratively (thus named “turbo”) until convergence is achieved. The performance of decoding is improved through this iterative procedure. Such a “turbo” principle of information processing has been applied in many other tasks such as multiuser detection and equalization. As we will see, it can also be used for system state estimation in a CPS.

软输出作为先验信息被馈送到解码器2中。 解码器2组合m,X2和来自解码器1的先验信息,还生成软输出。 然后,将解码器2的输出作为先验信息馈入解码器1。 反复重复此过程(因此称为“ turbo”),直到实现收敛。 通过此迭代过程可以提高解码性能。 信息处理的这种“ turbo”原理已被应用在许多其他任务中,例如多用户检测和均衡。 正如我们将看到的,它也可以用于CPS中的系统状态估计。

MODULATION

When the information bits are encoded into codewords (note that in some situations the channel coding procedure is not necessary), the procedure of modulation maps the abstract information to physical signals. In many typical communication systems, the information is conveyed by sinusoidal carriers, namely

当信息比特被编码为码字时(请注意,在某些情况下,不需要信道编码过程),调制过程会将抽象信息映射为物理信号。 在许多典型的通信系统中,信息是通过正弦载波传递的,即

where A, f , and φ are the amplitude, frequency, and phase of the sinusoidal signal, respectively. Hence the information can be carried in the amplitude, frequency or phase, thus resulting in the following types of modulation schemes: • Pulse amplitude modulation (PAM): There are M possible signal amplitudes, which represent log2 M bits. The simplest case is M = 2, namely the transmitter either transmits or not (A = 0), which is called on-off keying (OOK). • Frequency shift keying (FSK): The transmitter can choose one of M frequencies for the sinusoidal carrier signal. Hence each switch of the frequency represents log2 M bits. • Phase shift keying (PSK): The transmitter switches among M possible phases for transmitting log2 M bits. The above three typical modulation schemes can be combined; e.g., quadrature amplitude modulation (QAM) is a combination of PAM and PSK. To explain the mechanism of QAM, we consider the following signal:

其中A,f和φ分别是正弦信号的幅度,频率和相位。 因此,信息可以在振幅,频率或相位中传送,从而产生以下类型的调制方案:•脉冲振幅调制(PAM):有M种可能的信号振幅,代表log2 M位。 最简单的情况是M = 2,即发送器发送或不发送(A = 0),这称为开关键(OOK)。 •频移键控(FSK):发射机可以为正弦载波信号选择M个频率之一。 因此,每个频率开关代表log2 M位。 •相移键控(PSK):发送器在M个可能的相位之间切换,以发送log2 M位。 以上三种典型的调制方案可以结合使用; 例如,正交幅度调制(QAM)是PAM和PSK的组合。 为了解释QAM的机制,我们考虑以下信号:

which is decomposed to the quadrature and in-phase terms (A1 and A2 are the corresponding amplitudes). We can consider the carriers cos(2πft) and sin(2πft) as two orthogonal signals, each of which carries one branch of independent information. Hence (A1, A2) can be considered as a point in the signal plane (called a constellation), which is used to convey information. When there are M possible points in the constellation, we call the modulation scheme M-QAM. Fig. 2.7 shows illustrations of 16QAM and 64QAM.

它被分解为正交项和同相项(A1和A2是相应的幅度)。 我们可以将载波cos(2πft)和sin(2πft)视为两个正交信号,每个信号承载一个分支的独立信息。 因此,可以将(A1,A2)视为信号平面中的一个点(称为星座图),用于传递信息。 当星座中有M个可能的点时,我们将调制方案称为M-QAM。 图2.7显示了16QAM和64QAM的图示。

When selecting a suitable modulation scheme, there is a tradeoff between the transmission rate and transmission reliability. Usually, the symbol rate (i.e., the number of modulation signals transmitted in one second) is fixed. Hence if a denser constellation is used, more coded bits can be transmitted in the same time, thus improving the data transmission rate. However, the points in a dense modulation are close to each other, and thus can be confused by noise and results in transmission errors. As we will see in subsequent chapters, this tradeoff is important for the modulation selection in CPSs.

当选择合适的调制方案时,在传输速率和传输可靠性之间要权衡。 通常,符号率(即在一秒内发送的调制信号的数量)是固定的。 因此,如果使用更密集的星座,则可以同时发送更多的编码比特,从而提高了数据传输速率。 然而,密集调制中的点彼此靠近,因此可能被噪声混淆并导致传输错误。 正如我们将在后续章节中看到的那样,这种权衡对于CPS中的调制选择非常重要。

Estimation of the Rate-Distortion Function

Suppose a data string x n1 := ( x 1, x 2, . . . , x n ) is generated by a stationary memoryless source ( Xn ; n ≥ 1) with unknown marginal distribution P on a discrete alphabet A. In many theoretical and practical problems arising in a wide variety of scientific contexts, it is desirable – and often important – to obtain accurate estimates of the entropy H ( P ) of the source, based on the observed data x n1 ; see, for example, [35] [26] [30] [29] [32] [31] [8] and the references therein.

假设数据字符串x n1:=(x 1,x 2,…,xn)是由固定的无记忆源(Xn; n≥1)在离散字母A上具有未知的边际分布P生成的。 在广泛的科学环境中出现实际问题时,基于观察到的数据x n1,有必要-而且通常很重要-获得对源的熵H(P)的准确估计; 参见,例如,[35] [26] [30] [29] [32] [31] [8]及其引用。

Perhaps the simplest method is via the so-called plug-in estimator, where the entropy of P is estimated by H ( Px n1 ), namely, the entropy of the empirical distribution Px n1 of x n1 . The plug-in estimator satisfies the basic statistical requirement of consistency, that is, H ( PX n1 ) → H ( P ) in probability as n → ∞. In fact, it is strongly consistent; the convergence holds with probability one [2]. A natural generalization is the problem of estimating the rate-distortion function R (P, D ) of a (not necessarily discrete-valued) source. Motivation for this comes in part from lossy data compression, where we may need an estimate of how well a given data set could potentially be compressed, cf. [10], and also from cases where we want to quantify the “information content” of a particular signal, but the data under examination take values in a continuous (or more general) alphabet, cf. [27].

也许最简单的方法是通过所谓的插件估计器,其中P的熵由H(Px n1)估计,即x n1的经验分布Px n1的熵。 插入式估算器满足基本的统计一致性要求,即H(PX n1)→H(P)的概率为n→∞。 实际上,这是非常一致的; 收敛的可能性为1 [2]。 自然的概括是估算(不一定是离散值)源的速率失真函数R(P,D)的问题。 这样做的动机部分来自有损数据压缩,在这种情况下,我们可能需要估计给定数据集可能被压缩的程度,请参见。 [10],以及我们想量化特定信号的“信息内容”的情况,但是正在检查的数据采用连续(或更通用)字母的值,请参见。 [27]。

The rate-distortion function estimation question appears to have received little attention in the literature. Here we present some basic results for this problem. First, we consider the simple plug-in estimator R(PXn1 , D ), and determine conditions under which it is strongly consistent, that is, it converges to R (P, D ) with probability 1, as n → ∞. We call this the nonparametric estimation problem, for reasons that will become clear below

速率失真函数估计问题在文献中似乎很少受到关注。 在这里,我们介绍了此问题的一些基本结果。 首先,我们考虑简单的插件估计量R(PXn1,D),并确定其强一致的条件,即它以n =∞的概率1收敛到R(P,D)。 我们称其为非参数估计问题,原因如下所述

At first glance, consistency may seem to be a mere continuity issue: Since the empirical distribution PXn 1 converges, with probability 1, to the true distribution P as n → ∞, a natural approach to proving that R(PXn 1 , D) also converges to R(P, D) would be to try and establish some sort of continuity property for R(P, D) as a function of P.

乍一看,一致性似乎仅仅是一个连续性问题:由于经验分布PXn 1以概率1收敛到真实分布P为n→∞,因此自然证明了R(PXn 1,D) 收敛到R(P,D)将是尝试为R(P,D)建立某种作为P的函数的连续性。

But, as we shall see, R(PXn 1 , D) turns out to be consistent under rather mild assumptions, which are in fact too mild to ensure continuity in any of the usual topologies; see Section III-E for explicit counterexamples. This also explains our choice of the empirical distribution Px n 1 as an estimate for P: If R(P, D) was continuous in P, then any consistent estimator Pˆ n of P could be used to make R(Pˆ n, D) a consistent estimator for R(P, D). Some of the subtleties in establishing regularity properties of the rate-distortion function R(P, D) as a function of P are illustrated in [11] [1].

但是,正如我们将要看到的,在相当温和的假设下R(PXn 1,D)证明是一致的,实际上,这些假设太温和了,无法确保任何常用拓扑的连续性。 有关明确的反例,请参阅第III-E节。 这也解释了我们选择经验分布Px n 1作为对P的估计:如果R(P,D)在P中是连续的,则P的任何一致估计Pˆ n均可用于使R(Pˆ n,D) R(P,D)的一致估计量。 在[11] [1]中说明了建立速率失真函数R(P,D)的正则性作为P的一些微妙之处。

Another advantage of a plug-in estimator is that Px n 1 has finite support, regardless of the source alphabet. This makes it possible (when the reproduction alphabet is also finite) to actually compute R(Px n 1 , D) by approximation techniques such as the Blahut-Arimoto algorithm [7] [3] [12]. When the reproduction alphabet is continuous, the Blahut-Arimoto algorithm can still be used after discretizing the reproduction alphabet; the discretization can, in part, be justified by the observation that it can be viewed as an instance of the parametric estimation problem described below. Other possibilities for continuous reproduction alphabets are explored in [33] [5]. The consistency problem can be framed in the following more general setting. As has been observed by several authors recently, the rate-distortion function of a memoryless source admits the decomposition,

插件估算器的另一个优点是Px n 1具有有限的支持,而与源字母无关。 这使得有可能(当再现字母也是有限的时候)通过诸如Blahut-Arimoto算法[7] [3] [12]之类的近似技术实际计算R(Px n 1,D)。 当再现字母是连续的时,在离散化再现字母后仍然可以使用Blahut-Arimoto算法; 离散化可以部分地通过以下观察来证明是正确的:可以将其视为以下所述的参数估计问题的一个实例。 在[33] [5]中探索了连续再现字母的其他可能性。 一致性问题可以在以下更一般的设置中进行描述。 正如最近几位作者所观察到的,无记忆源的速率失真函数允许分解,

\where the infimum is over all probability distributions Q on the reproduction alphabet, and R(P, Q, D) is the rate achieved by memoryless random codebooks with distribution Q used to compress the source data to within distortion D; see, e.g., [36] [15]. Therefore, R(P, D) is the best rate that can be achieved by this family of codebooks. But in the case where we only have a restricted family of compression algorithms available, indexed, say, by a family of probability distributions {Qθ ; θ ∈ Θ} on the reproduction alphabet, then the best achievable rate is:

\其中极小值是再现字母表上所有概率分布Q的总和,R(P,Q,D)是无记忆随机码本所获得的速率,其分布Q用于将源数据压缩到失真D之内; 参见,例如,[36] [15]。 因此,R(P,D)是该系列码本可以达到的最佳速率。 但是,在我们只有有限的压缩算法系列的情况下,可以用一系列概率分布{Qθ; 在复制字母上,则可达到的最佳速率为:

We also consider the parametric estimation problem, namely, that of establishing the strong consistency of the corresponding plug-in estimator RΘ(PXn 1 , D) as an estimator for RΘ(P, D). It is important to note that, when Θ indexes the set of all probability distributions on the reproduction alphabet, then the parametric and nonparametric problems are identical, and this allows us to treat both problems in a common framework.

我们还考虑了参数估计问题,即建立相应的插件估计器RΘ(PXn 1,D)的强一致性作为RΘ(P,D)的估计器。 重要的是要注意,当Θ索引了再现字母上所有概率分布的集合时,参数和非参数问题都是相同的,这使我们能够在一个通用框架中处理这两个问题。

Our two main results, Theorems 4 and 5 in the following section, give regularity conditions for both the parametric and nonparametric estimation problems under which the plug-in estimator is strongly consistent. It is shown that consistency holds in great generality for all distortion values D such that RΘ(P, D) is continuous from the left. An example illustrating that consistency may actually fail at those points is given in Section III-D.

下节的定理4和定理5是我们的两个主要结果,给出了参数估计和非参数估计问题的正则条件,在这些条件下插件估计量是非常一致的。 结果表明,一致性对于所有失真值D都具有很大的通用性,因此RΘ(P,D)从左侧开始连续。 第III-D节给出了一个示例,说明一致性实际上可能在这些点上失败。

In particular, for the nonparametric estimation problem we obtain the following three simple corollaries, which cover many practical cases. Corollary 1: If the reproduction alphabet is finite, then for any source distribution P, R(PXn 1 , D) is strongly consistent for R(P, D) at all distortion levels D ≥ 0 except perhaps at the single value where R(P, D) transitions from being finite to being infinite. Corollary 2: If the source and reproduction alphabets are both equal to R d and the distortion measure is squared-error, then for any source distribution P and any distortion level D ≥ 0, R(PXn 1 , D) is strongly consistent for R(P, D). Corollary 3: Assume that the reproduction alphabet is a compact, separable metric space, and that the distortion measure ρ(x, ·) is continuous for each x ∈ A.

特别是,对于非参数估计问题,我们获得以下三个简单的推论,它们涵盖了许多实际案例。 推论1:如果再现字母是有限的,那么对于任何源分布P,在所有失真等级D≥0处,R(PXn 1,D)对于R(P,D)都是非常一致的,除了在单个值处,R( P,D)从有限过渡到无限。 推论2:如果源字母和再现字母都等于R d且失真度为平方误差,则对于任何源分布P和任何失真水平D≥0,R(PXn 1,D)对于R都是强一致的 (P,D)。 推论3:假设再现字母是一个紧凑的,可分离的度量空间,并且对于每个x∈A,失真度量ρ(x,·)是连续的。

Leave a Reply