Channel error rate optimization using Markov codes

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A system for optimizing an error rate of data through a communication channel, the system comprising:
 a data generator operable to generate a training sequence as a Markov code, and to propagate the training sequence through the communication channel;
a Soft Output Viterbi Algorithm (SOVA) detector operable to estimate data values of the training sequence after propagation through the communication channel; and
an optimizer operable to compare the estimated data values to the generated training sequence, to determine an error rate based on the comparison, and to change the training sequence based on the Markov code to lower the error rate of the data through the communication channel.
1 Assignment
0 Petitions
Accused Products
Abstract
In one embodiment, a system provides for optimizing an error rate of data through a communication channel. The system includes a data generator operable to generate a training sequence as a Markov code, and to propagate the training sequence through the communication channel. The system also includes a Soft Output Viterbi Algorithm (SOVA) detector operable to estimate data values of the training sequence after propagation through the communication channel. The system also includes an optimizer operable to compare the estimated data values to the generated training sequence, to determine an error rate based on the comparison, and to change the training sequence based on the Markov code to lower the error rate of the data through the communication channel.
11 Citations
No References
HIDDEN MARKOV MODEL DETECTION FOR SPREAD SPECTRUM WAVEFORMS  
Patent #
US 20110222584A1
Filed 03/11/2010

Current Assignee
Harris Corporation

Sponsoring Entity
Harris Corporation

Method of refining statistical pattern recognition models and statistical pattern recognizers  
Patent #
US 7,509,259 B2
Filed 12/21/2004

Current Assignee
Google Technology Holdings LLC

Sponsoring Entity
Motorola Inc.

SourceChannel Approach to Channel Coding with Side Information  
Patent #
US 20070217522A1
Filed 03/09/2007

Current Assignee
Texas AM University System

Sponsoring Entity
Texas AM University System

Signal conditioned minimum error rate training for continuous speech recognition  
Patent #
US 5,806,029 A
Filed 09/15/1995

Current Assignee
Nuance Communications Inc.

Sponsoring Entity
ATT Inc.

Information recording and reproducing apparatus and method and signal decoding circuit  
Patent #
US 20030026028A1
Filed 10/29/2001

Current Assignee
Toshiba Storage Device Incorporated

Sponsoring Entity
Fujitsu Limited

SOURCECHANNEL APPROACH TO CHANNEL CODING WITH SIDE INFORMATION  
Patent #
US 20110311003A1
Filed 08/29/2011

Current Assignee
Texas AM University System

Sponsoring Entity
Texas AM University System

Method and System for Selectively Biased Linear Discriminant Analysis in Automatic Speech Recognition Systems  
Patent #
US 20140058731A1
Filed 08/23/2013

Current Assignee
Genesys Telecommunications Laboratories Incorporated

Sponsoring Entity
Genesys Telecommunications Laboratories Incorporated

WynerZiv coding based on TCQ and LDPC codes  
Patent #
US 8,207,874 B2
Filed 08/04/2008

Current Assignee
Texas AM University System

Sponsoring Entity
Texas AM University System

TRAINING MARKOV RANDOM FIELDBASED TRANSLATION MODELS USING GRADIENT ASCENT  
Patent #
US 20140365201A1
Filed 02/18/2014

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Technology Licensing LLC

Universal modulation coding for a data channel  
Patent #
US 8,976,474 B1
Filed 10/03/2013

Current Assignee
Seagate Technology LLC

Sponsoring Entity
Seagate Technology LLC

SYSTEM AND METHOD FOR COMMUNICATION  
Patent #
US 20150323989A1
Filed 05/08/2015

Current Assignee
Barron Associates Inc

Sponsoring Entity
Barron Associates Inc

20 Claims
 1. A system for optimizing an error rate of data through a communication channel, the system comprising:
a data generator operable to generate a training sequence as a Markov code, and to propagate the training sequence through the communication channel; a Soft Output Viterbi Algorithm (SOVA) detector operable to estimate data values of the training sequence after propagation through the communication channel; and an optimizer operable to compare the estimated data values to the generated training sequence, to determine an error rate based on the comparison, and to change the training sequence based on the Markov code to lower the error rate of the data through the communication channel.  View Dependent Claims (2, 3, 4, 5, 6, 7)
 8. A method of optimizing an error rate of data through a communication channel, the method comprising:
generating a training sequence as a Markov code; propagating the training sequence through the communication channel; estimating, with a Soft Output Viterbi Algorithm (SOVA) detector, data values of the training sequence after propagation through the communication channel; comparing the estimated data values to the generated training sequence; determining an error rate based on the comparison; and changing the training sequence based on the Markov code to lower the error rate of the data through the communication channel.  View Dependent Claims (9, 10, 11, 12, 13, 14)
 15. A nontransitory computer readable medium comprising instructions that, when executed by a processor, are operable to direct the processor to optimize an error rate of data through a communication channel, the instructions further directing the processor to:
generate a training sequence as a Markov code source; propagate the training sequence through the communication channel; estimate, with a Soft Output Viterbi Algorithm (SOVA) detector, data values of the training sequence after propagation through the communication channel; compare the estimated data values to the generated training sequence; determine an error rate based on the comparison; and change the training sequence based on the Markov code to lower the error rate of the data through the communication channel.  View Dependent Claims (16, 17, 18, 19, 20)
1 Specification
This patent application claims priority to, and thus the benefit of an earlier filing date from, U.S. Provisional Patent Application No. 62/375,239 (filed Aug. 15, 2016), the entire contents of which are hereby incorporated by reference.
In one embodiment, a system provides for optimizing an error rate of data through a communication channel. The system includes a data generator operable to generate a training sequence as a Markov code, and to propagate the training sequence through the communication channel. The system also includes an equalizer/Soft Output Viterbi Algorithm (SOVA) detector operable to estimate data values of the training sequence after propagation through the communication channel. The system also includes an optimizer operable to compare the estimated data values to the generated training sequence, to determine an error rate based on the comparison, and to change the training sequence based on the Markov code to lower the error rate of the data through the communication channel.
The various embodiments disclosed herein may be implemented in a variety of ways as a matter of design choice. For example, some embodiments herein are implemented in hardware whereas other embodiments may include processes that are operable to implement and/or operate the hardware. Other exemplary embodiments, including software and firmware, are described below.
Some embodiments are now described, by way of example only, and with reference to the accompanying drawings. The same reference number represents the same element or the same type of element on all drawings.
The figures and the following description illustrate specific exemplary embodiments. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody certain principles and are included within the scope of this disclosure. Furthermore, any examples described herein are intended to aid in understanding the principles of the embodiments and are to be construed as being without limitation to such specifically recited examples and conditions. As a result, the embodiments are not limited to the examples described below.
The capacity of a communication channel was formalized by Claude Shannon in his 1948 treatise “A Mathematical Theory of Communication”. In that treatise, Shannon provided a formula to compute channel capacity based on the maximization of mutual information between a channel input and the channel output over source probability distributions. The channel capacity imposes a fundamental bound on the maximum throughput performance of reliable communication with any error correcting code.
Computing the capacity of a communication channel is an interesting theoretical problem in its own right. One example includes the BlahutArimoto algorithm which has been devised to compute channel capacity of discrete memoryless channels as well as channels with memory, such as the magnetic recording channel of a disk drive. However, knowing the theoretical channel capacity does not immediately render how to achieve a maximum throughput with a practical error correcting code, which is a primary focus of coding theory. More recently, coding theorists have designed error correcting codes to closely approach the Shannon limit of channel capacity for certain channels.
Based on the notion of channel capacity, systems and methods presented herein are operable to optimize a channel input (i.e., a source) probability distribution function (PDF) to maximize the capacity of the channel. In this regard, a new source optimization is implemented based on a previously unused metric, such as the detection error rate (BER/SER). The problem employs a constraint on the minimum source rate H(X)≥h_{0 }so as to prevent a trivial solution. However, h_{0 }can be viewed as free design parameter to allow for more design flexibility. Another advantage of using a metric such as the SER is that it uses a simpler detector (Viterbi or SOVA detector) as opposed to a soft output symbol detector, such as a BCJR detector (BahlCockeJelinekRaviv detector), which is used for the capacity metric.
With this in mind, systems and methods presented herein provide for the optimization of error rates in a channel, such as bit error rates (BERs) and symbol error rates (SERs). For example, solutions for channels, with or without memory, are provided herein along with the implementation of an iterative algorithm to optimize the error rate for the channel.
However, measuring the channel capacity does not always, in practice, accurately determine the amount of recoverable data that may pass through the channel. And, the channel'"'"'s characteristics may change over time and/or even across its physical properties. For example, a hard disk drive (e.g., a channel with memory) may comprise a plurality of sectors where data is stored. Each sector of the hard disk drive may be thought of as unique channel because, among other reasons, each sector may comprise different physical properties from the next sector. Accordingly, each sector on the hard disk drive may vary in terms of capacity from one sector to the next.
The system 100 optimizes the data throughput of the channel 103 by optimizing the error rate of the channel 103 with a training sequence. Once the error rate of data through the channel 103 is optimized, actual data can be configured to mimic the data of the training sequence so as to reduce its error rate through the channel 103 and thereby effectively reduce the amount of error correction used to recover the data from the channel 103.
The system 100 starts the optimization by generating an initial source model 101 that is fed into a source generator 102. The source generator 102 generates the training sequence x_{n }based on the initial source model 101 and propagates the training sequence x_{n }through the channel 103. The channel 103, having an effect on the training sequence x_{n }(i.e., the channel 103 introduces errors), results in a noisy observation sequence y_{n }that is processed by an equalizer/SOVA detector 104.
The equalizer/SOVA detector 104 is a variant of the classical Viterbi algorithm. SOVA detectors have been used for years in the disk drive industry and can be implemented efficiently in a variety ways as a matter design choice. The equalizer/SOVA detector 104 differs from the classical Viterbi algorithm in that it uses a modified path metric which takes into account the a priori probabilities of input symbols, and produces a “soft output” indicating the reliability of the decision. And, the equalizer provides equalization of the signal prior to SOVA detection.
The equalizer/SOVA detector 104 processes the noisy training sequence y_{n }to generate an estimated sequence {circumflex over (x)}_{n }. The optimizer 105 compares the sequence {circumflex over (x)}_{n }to the original training sequence x_{n }and outputs a new Markov source model Q_{ij }to the source generator 102, while also tracking the error rate (e.g., BER and/or SER) through the channel 103 during each iteration. The quantity Q_{ij}, represents the probability of starting from the detector trellis states i and going to state j and fully describes the Markov source model. The source generator 102 then changes its output training sequence x_{n }based on the new source model Q_{ij }from the optimizer 105. When the lowest error rate has been obtained (e.g., after the last iteration), the channel 103 has been characterized and optimized in terms of its error rate such that data and error correction can be configured accordingly for propagation through the channel 103 and recovered therefrom.
More specifically, once the error rate of the channel 103 is optimized, subsequent data through the channel 103 can be similarly configured to have a comparable error rate. Thus, error correction codes can be tailored for that identified error rate instead of generically blanketing the data with error correction. This process may result in a lower data rate than previous systems. However, as less error correction may be used, the actual data throughput across the channel 103 may increase, in some instances significantly.
In the process element 203, the equalizer/SOVA detector 104 estimates data values of the input training sequence after the propagation through the communication channel 103. The optimizer 105 then compares the estimated data values to the generated training sequence from the source generator 102, in the process element 204, to determine an error rate of the data propagating through the channel 103, in the process element 205. That is, the optimizer 105 compares the original training sequence x_{n }to the estimated values of the training sequence {circumflex over (x)}_{n}. The optimizer 105 then determines the error rate based on the comparison. The optimizer 105 compares that error rate with the previous iteration to determine if it has settled to a minimum, in the process element 206.
If the error rate is lower, the optimizer 105 outputs the model Q_{ij }that operates as a new input model to the source generator 102. In this regard, the optimizer 105 directs the source generator 102 to change the training sequence x_{n }via the change in the Markov source model in an attempt to lower the error rate of the data through the communication channel 103, in the process element 208. And, the process 200 returns to the process element 201 to thus generate the new training sequence for the channel 103. If, however, the error rate has settled to a minimum (e.g., nearly the same as the previous error rate), in the process element 206, the optimizer 105 may use the last iteration of the training sequence, in the process element 207, as a basis for characterizing the channel 103 in terms of its error rate. In this regard, the optimizer 105 may also use this model of the Markov chain to configure subsequent actual data through the channel 103 as well as error correction with that data.
The embodiments shown and described herein may be implemented for memoryless channels and/or channels with memory. In some embodiments, the system 100 may be implemented as firmware within a disk drive system (i.e., channel with memory) to characterize the disk drive, and/or various sectors and regions thereof, in terms of its bit error rate. Then, coding techniques can be applied based on that bit error rate, including precoding and error correction coding, that configure how the data is to be written to and recovered from the disk drive. Other exemplary embodiments are shown and described in greater detail below.
Source Optimization Based on SER Metric
In this embodiment, Markov code source optimization is based on an error rate metric of the channel 103. More specifically, the system 100 is operable to find a Markov source model that minimizes the detected symbol error rate P_{e }with a lower limit constraint on the source rate (e.g., entropy) H(X). For example, the system 100 is operable to:
where h_{0 }is a minimum allowed source rate. A constraint on the source rate H(X), in this embodiment, is used because it would obtain a trivial solution of P_{e}=0 when H(X)=0 without it. Accordingly, a solution is sought in the space of Markov source models Q_{ij}=μ_{i}P_{ij}, where P_{ij }is the Markov transition probability from trellis state i to state j, and μ_{i }is the steady state probability of trellis state i. In this regard, a first solution for memoryless channels is presented as it is generally an easier problem than the case of channels with memory.
Memoryless Channel
Consider the source optimization problem for a discrete memoryless channel having an input alphabet and an output alphabet . The expression for the detected SER is the expected value (e.g., over ) of the given that a particular symbol x from was transmitted. In other words,
P_{e}=P(x)E(x), Eq. 2.
where E(x)=P({circumflex over (x)}≠xx transmitted) and denotes the conditional SER given that the symbol x is transmitted and detected as {circumflex over (x)}≠x. One example includes the maximum a posteriori (MAP) detector that is optimal in terms of the SER metric. It produces an output {circumflex over (x)} that maximizes the probability P(xy)∝P(x)P(yx) over all x∈ as follows:
Based on the probability density function P(xy), the output alphabet is partitioned into decision regions (x) (e.g., “Voronoi cells”) for each input symbol x as shown in
such that
H(X)−Σ_{x}P(x)log_{2}P(x)≥h_{0}. Eq. 5.
Assuming that the “Efactors” E(x) are fixed quantities, an optimizing P(X) can be found by solving the following set of nonlinear equations:
P(x)=Z^{−1}2^{−E(x)/λ}, Eq. 6.
Z=Σ_{x}2^{−E(x)/λ}, Eq. 7.
and
h_{0}=−Σ_{x}P(x)log_{2}P(x), Eq. 8.
where the auxiliary parameter λ>0 is the Lagrange multiplier associated with the entropy constraint.
However, E(x) does not generally remain constant since they depend implicitly on P(X), and altering it will cause E(x) to change too. Accordingly, the system 100 employs an iterative algorithm where, in each iteration, the Efactors are computed based on the current source model from the source generator 102. The source generator 102 is then updated treating the Efactors as constant. Such is summarized in the algorithm below:
 First, initialize source P(X) (e.g., an initial input 101 of independent, identically distributed “IID” random variables).
 Then, repeat the following steps until convergence
 Estimate Efactors E(x) for current source P(X); and
 Treating E(x) as fixed, update P(X) to minimize P_{e}.
Channels with Memory
For the general case of Markov source optimization for channels with memory and for a given Markov source model Q_{ij}=μ_{i}P_{ij}, the SER can be linearly approximated in a manner similar to Equation 3 as:
P_{e}=Σ_{i,j}Q_{ij}E_{ij}, Eq. 9.
for suitable coefficients E_{ij}. The estimation of these coefficients is implemented via training. Therefore, the source optimization problem of Equation 1 becomes
such that
H(X)−Σ_{i,j}Q_{ij }log_{2}P_{ij}≥h_{0}. Eq. 11.
Again, assuming that the Efactors E_{ij }are fixed quantities, it can be shown that the optimal Markov source model can be obtained. For example, let λ>0 denote the as yet unknown Lagrange multiplier associated with the entropy constraint. Then, construct a “noisy” adjacency matrix A_{ij}=2^{−E}^{ij}^{/λ}, and compute the optimal Markov model as follows:
where u and v are respectively the left and right eigenvectors of A corresponding to its largest eigenvalue λ_{max}. Afterwards, λ is chosen to satisfy the source entropy constraint as follows:
h_{0}=−Σ_{i,j}μ_{i}P_{ij }log_{2}P_{ij}. Eq. 13.
This is a boundary solution in the sense that the source rate inequality constraint is in fact satisfied with an equality. The solution is found using a standard nonlinear equation solver.
Estimation of the Efactors E_{ij }can be obtained through training. Generally, in practice, the Efactors E_{ij }are difficult to compute analytically. A stochastic estimate for E_{ij }using training data is presented. In this regard, let the sequence x_{1}^{N }of length N denote the input to the channel 103 and the sequence {circumflex over (x)}_{1}^{N }denote the output of the equalizer/SOVA detector 104 (i.e., the detected training sequences). Also, let ε_{n}=Π(x_{n}≠{circumflex over (x)}_{n}) denote the error indicator sequence, and w_{H}(⋅) be the Hamming weight function. Thus, as described in greater detail in the below:
E_{ij}=E_{ij}^{a}−E_{i}^{b}, Eq. 14.
where
for a window size parameter J that is typically chosen as a small integer.
In the summation of Eq. 15, all time indices n are observed where state s_{n−}=i to the state s_{n}=j. For those indices, the number of errors found in the subsequence {ε_{n−J}, . . . , ε_{n−J+M}} are accumulated and a local neighborhood of time index n is identified. Likewise with Eq. 16, the number of errors found in {ε_{n−J+1}, . . . , ε_{n−J+M}} are accumulated as the system 100 passes through state s_{n}=i at time n. Both expressions are relatively straightforward computations involving pattern matching and accumulation of error weights. This algorithm can be summarized as follows.
 First, initialize Markov source Q_{ij }(e.g., an initial input 101 of IID random variables).
 Then repeat the following steps until convergence:
 Generate training sequence x_{1}^{N }from source Q_{ij};
 Pass x_{1}^{N }through channel and detector to get {circumflex over (x)}_{1}^{N};
 Estimate Efactors E_{ij}=E_{ij}^{a}−E_{i}^{b }using Eqs. 15 and 16; and
 Solve optimization problem of Eq. 10 to obtain a new Q_{ij}.
Postcoding (e.g., postcoder 120) results in bits that are not constrained. These bits are then transferred to a Low Density Parity Check (LDPC) encoder 121 to add parity 129 for error correction. The precoder 122 provides returns the bits to their constrained form with parity bits 129. Precoding by the precoder 122 can be used to improve performance. The BER in the postcoded domain 127 (e.g., using bits a_{n }and â_{n}) is minimized while maintaining the Markov property in the precoded domain bits x_{n }(e.g., on the media), excluding the parity bits 129 added by the LDPC encoder 121.
The equalizer/SOVA detector 104 and the channel 103 generally constitute an environment from the point where the bits are transmitted or written onto media, such as a storage device (e.g., disk drive or solid state drive—“SSD”), to the point where they are received and detected. The LDPC decoder 123 and the precoder 124 return the sequence to its form after the effects of the LDPC encoder 121 and the postcoder 120. The only change to the algorithm is that the system 100 computes the error vector based on the postcoded bits, i.e., ε_{n}=Π(a_{n}≠â_{n}), again excluding the parity bits 129. The Markov source decoder 125 then extracts the Markov code to reveal underlying data.
The optimizer 105 computes the Efactors E_{ij }from the error vector ε_{n }and computes new source probabilities Q_{ij }by solving Equation 10. This generally involves finding the largest eigenvalue of a matrix and solving nonlinear equations. Hence, the calculations may be more suitable for implementation in firmware or as an offline calibration, but specialized hardware implementation is also possible. The free parameter h_{0 }controls the source rate and yields an extra degree of design flexibility.
The source generator 105 can be initialized with an IID model (e.g., with all states being equally probable). Alternatively, in a magnetic recording system, different disc drives or even different zones on a given disc may have different optimal Markov sources, owing to their different signal/noise statistics. These different Markov models may, however, be similar enough that the source generator 102 could start with a relatively good/common initial solution such that the optimizer 105 can “fine tune” the initial code separately for each drive or zone within a relatively small number of iterations.
The system 100 can be used with any alternative cost function (instead of the SER) when it is expressed in a linear form similar to Equation 5. For example, the system 100 can minimize the conditional entropy H(XY) of input X given the output Y. This cost function represents the uncertainty in X given Y. To implement such, the system 100 sets E_{ij}=−T_{ij}, where T_{ij }are the Tfactors of a generalized BlahutArimoto algorithm defined as:
T_{ij}=Σ_{y}P(ys_{n−1}^{n}=(i,j))log_{2}P(s_{n−1}^{n}=(i,j)y)−Σ_{y}P(ys_{n}=i)log_{2}P(s_{n}=iy) Eq. 17.
This approach maximizes the channel capacity but with the source rate being specified explicitly as: H(X)=h_{0}.
The following is an example Markov source designed for magnetic recording channels, specifically for a drive having a channel bit density (CBD) of 2.8. Here, the goal was to optimize the Markov code having the same source rate as a maximum transition run (MTR) constraint code of K=3, but with a better BER performance. The MTR code, which is commonly used in magnetic recording, limits the number of consecutive transition in the source sequence to K=3 and has a source rate of H_{MTR3}=0.94678 bits. The motivation for such a design is that it would be a dropin replacement for the MTR3 code, due to its identical source rate, without requiring changes to other system parameters such as the CBD and LDPC code rates.
The BER minimizing source optimizer was implemented with the setting of h_{0}=H_{MTR3}=0.94678 starting from an IID source model.
Expression for P_{e }
One goal is to show that the probability of detection error P_{e }can be expressed approximately as Eq. 9 to derive explicit formulas for Et_{ij}. For example, let x_{1}^{N }and {circumflex over (x)}_{1}^{N }denote the channel input and SOVA detected output training sequences. It can then be assumed that the probability of x_{n }being detected incorrectly depends strongly only on a “local neighborhood” consisting of a (2J+1) symbol subsequence Π_{n}=x_{n−J}^{n+J }for a suitable window size parameter J as follows:
P({circumflex over (x)}_{1}^{N}≠x_{n}x_{1}^{N})≈P({circumflex over (x)}_{1}^{N}≠x_{n}Π_{n})E(Π_{n}). Eq. 18.
This approximation is used to limit the computational complexity of the algorithm. By ergodicity, a statistical estimate for E(Π) for each symbol pattern Π of length 2J+1 is:
where Π(⋅) is the indicator function. Then, the SER expression is:
P_{e}=Σ_{Π}P(Π)E(Π). Eq. 20.
Note that the symbol subsequence Π=π_{0}^{2J }is equivalent to a subsequence α_{0}^{2J−M+1 }of an Mbit detector trellis states α_{k}π_{k}^{k+M−1}. Therefore, the Markov source model Q_{ij}=μ_{i}P_{ij }for the source generator 102 implies that:
P(Π)=P(α_{0}^{2J−M+1})=Π_{k+0}^{2J−M}Q_{α}_{k}_{,α}_{k+1}Π_{k=1}^{2J−M}μ_{α}_{k}^{−1}, Eq. 21.
Since the probability P(Π), and hence P_{e}, are both nonlinear functions of the Markov probabilities, an approximate expression for P_{e }can be derived by linearizing near a given source Q_{ij}=μ_{i}P_{ij}. In this regard, the derivative of log P(Π) at the current model Q_{ij}=μ_{i}P_{ij }can be computed as:
δ log P(Π)≈Σ_{k=0}^{2J−M}δ log Q_{α}_{k}_{,α}_{k+1}−Σ_{k=1}^{2J−M}δ log μ_{α}_{k}. Eq. 22.
Therefore,
So, P_{e }can be approximated at the current model Q_{ij}=μ_{i}P_{ij }as follows:
This yields the desired form for P_{e }as follows:
P_{e}≈Σ_{ij}E_{ij}^{a}Q_{ij}−Σ_{i}E_{i}^{b}μ_{i}≡Σ_{ij}E_{ij}Q_{ij}, Eq. 25.
where E_{ij}=E_{ij}^{a}−E_{i}^{b}. With U(Π)E(Π)P(Π), it can be readily seen that
To illustrate, consider a binaryinput channel with a trellis memory of M=4 and a window size parameter of J=3. Then, Π is a 7bit pattern consisting of 4 adjacent trellis states, Π≡(α, β, γ, δ). This means that the following expression for P(Π) is:
Assuming that E(Π)=E(αβγδ) has been estimated, Equations 26 and 27 may be computed as Equations 29 and 30 as follows:
where U(αβγδ)=E(αβγδ)P(αβγδ).
Training Based Estimation of E_{ij }
In this section, it is illustrated how E(Π) and E_{ij }can be estimated from training data. For example, let ε_{n}=Π(x_{n}≠{circumflex over (x)}_{1}^{N}) denote the bit error sequence and let w_{H}(⋅) denote the Hamming weight. A stochastic (e.g., training based) estimate of E(Π) is then given by
Inserting Equation 31 into Equation 26 yields
which can be rewritten as
Similarly, inserting Equation 31 into Equation 27 and proceeding as before:
And then, the Efactors can be estimated using E_{ij}=E_{ij}^{a}−E_{i}^{b}.
The embodiments can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. One embodiment disclosed herein is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.
Furthermore, the embodiments can take the form of a computer program product accessible from the computer readable medium 306 providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, the computer readable medium 306 can be any apparatus that can tangibly store the program for use by or in connection with the instruction execution system, apparatus, or device, including the computer system 300.
The medium 306 can be any tangible electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device). Examples of a computer readable medium 306 include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a readonly memory (ROM), a rigid magnetic disk and an optical disk. Some examples of optical disks include compact diskread only memory (CDROM), compact diskread/write (CDR/W) and DVD.
The computing system 300, suitable for storing and/or executing program code, can include one or more processors 302 coupled directly or indirectly to memory 308 through a system bus 310. The memory 308 can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices 304 (including but not limited to keyboards, displays, pointing devices, etc.) can be coupled to the system either directly or through intervening I/O controllers. Network adapters may also be coupled to the system to enable the computing system 300 to become coupled to other data processing systems, such as through host systems interfaces 312, or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.