Methods and devices for two-dimensional iterative multi-track based map detection

[0001] Two-dimensional (2-D) intersymbol-interference (ISI) channels have become practically relevant in various data recording technologies such as two-dimensional magnetic recording (TDMR), optical holographic memories as well as in other areas such as pixelated wireless optical channels and 2-D grid networks. From a signal processing viewpoint, data recording systems in 2-D have advantages over traditional 1-D systems. 2-D recording systems are less sensitive to timing instabilities due to wider tracks and hence not restrictive to the size of sensory read elements. With clever 2-D signal processing, guard bands between tracks can be avoided. This improves format efficiency. Lastly, if 2-D ISI can be handled beneficially to gain signal-to-noise ratio (SNR) by appropriate signal processing.

[0011] The emergence of 2-D ISI channels motivates the development of 2-D signal processing techniques for combatting ISI. There is a wide spectrum of 1-D detection techniques ranging from decision feedback equalization (DFE) to the optimal maximum a-posteriori (MAP) algorithm that can be extended to the 2-D case. 2-D DFE based methods are easy to implement but suffer from error propagation. The 1-D MAP algorithm is theoretically optimal and is the best-in-class detector for minimizing bit-error rate. However, unlike 1-D MAP detection that can be easily realized, 2-D MAP detection is in general NP-complete. It is difficult to realize a 2-D trellis that spans signal dimensions over 2-D blocks of data greater than just a few bits. Low complexity 2-D signal detection algorithms based on 1-D schemes are needed to approach 2-D MAP detection performance. Several authors have considered various approaches towards 2-D detection. Nelson et al. (J. K. Nelson, A. C. Singer, and U. Madhow, “Multi-directional Decision Feedback for 2D Equalization,” in Proc. IEEE Intl. Conf. on Acoust. Speech and Signal Proc. ICASSP'04, vol. 4, pp. 921-924, May 2004) derived a multi-dimensional decision feedback scheme for 2-D equalization. Wu et al. (Y. Wu, J. A. O'Sullivan, R. S. Indeck, and N. Singla, “Iterative Detection and Decoding for Seperable Two-Dimensional Intersymbol Interference,” IEEE Trans. Magn., vol. 39, pp. 2115-2210, July 2003) developed 2-D iterative detection and decoding scheme for a separable 2-D ISI system. However, in most practical systems, 2-D ISI is not separable. Shental et al. (O. Shental, N. Shental, S. Shamai, I. Kanter, A. J. Weiss, and Y. Weiss, “Discrete-Input Two-Dimensional Gaussian Channels With Memory: Estimation and Information Rates via Graphical Models and Statistical Mechanics,” IEEE Trans. Inform. Theory., vol. 54, pp. 1500-1513, April 2008) developed a generalized belief propagation approach that achieves near ML performance for 2-D ISI channels. Simulations in Shental et al. considered (20×20) 2-D data sizes with smaller 2-D ISI masks (2×2) and low energy distribution on side taps; such cases are easily handled since nearby boundary conditions can aid the estimation algorithm. In a recent prior work, Chen et al. (Y. Chen, T. Cheng, P. Njeim, B. Belzer, and K. Sivakumar, “Iterative Soft Decision Feedback Zig-Zag Equalizer for 2D Intersymbol Interference Channels,” IEEE Jour. on Sel. Areas in Comm., vol. 28, pp. 167-180, February 2010) developed an iterative soft-decision feedback zig-zag MAP algorithm. This method demonstrated performance close to nearly optimal detection and compared well with the method in Shental et al.

[0012] Some embodiments are directed to methods and systems for encoding and decoding data, including but not limited to data stored in a data storage device such as a disk drive. FIG. 1 shows the principal components of an exemplary magnetic disk drive 100 constructed in accordance with one embodiment. With reference to FIG. 1, the disk drive 100 comprises a head disk assembly (HDA) 144 and a printed circuit board assembly (PCBA) 141. The HDA 144 includes a base 161 and a cover 171 attached to the base 161 that collectively house a disk 102 (or a stack of two or more such disks 102), a spindle motor 113 attached to the base 161 for rotating the disk 102, an HSA 150, and a pivot bearing cartridge 184 (such as a stainless steel pivot bearing cartridge, for example) that rotatably supports the head stack assembly (HSA) 150 on the base 161. The spindle motor 113 rotates the disk 102 at a constant angular velocity. The HSA 150 comprises a swing-type or rotary actuator assembly 152, at least one head gimbal assembly (HGA) 110 coupled to the load beam 303 that includes a flexure constructed as described above, and a flex circuit cable assembly. The rotary actuator assembly 152 includes a body portion, at least one actuator arm cantilevered from the body portion, and a coil portion 156 cantilevered from the body portion in an opposite direction from the actuator arm. The actuator arm supports the HGA 110 that, in turn, includes and supports the slider(s). The flex circuit cable assembly may include the flexible cable 180 and a flex clamp 159. The flexible cable 180 and the flexure of the HGA 110 are structured and coupled in the manner described above. The HSA 150 is pivotally secured to the base 161 via the pivot-bearing cartridge 184 so that the slider at the distal end of the HGA 110 may be moved over the surfaces of the disk(s) 102. The pivot-bearing cartridge 184 enables the HSA 150 to pivot about a pivot axis. The storage capacity of the HDA 144 may be increased by, for example, increasing the track density (the TPI) on the disk 102 and/or by including additional disks 102 in a disk stack and by an HSA 150 having a vertical stack of HGAs 110 supported by a rotary actuator assembly 152 having multiple actuator arms. The “rotary” or “swing-type” actuator assembly 152 rotates on the pivot bearing 184 cartridge about its pivot axis between limited positions and further includes a coil portion 156 that extends from one side of the body portion to interact with one or more permanent magnets 190 mounted to back irons 170, 172 to form a voice coil motor (VCM). The VCM causes the HSA 150 to pivot about the actuator pivot axis to cause the slider and the read-write transducers thereof to sweep radially over the disk(s) 102. The PCBA 141 includes control circuitry configured to read data from and write data to the disk(s) 102. When reading data from the disk(s) 102, a read channel typically samples the read signal to generate sample is values that are equalized into a target response (e.g., a target partial response). A sequence detector detects an estimated data sequence from the equalized samples. According to one embodiment, one component of the control circuitry of the PCBA 141 that handles the data channel includes a multi-row/multi-column MAP detector. Indeed, one embodiment is an iterative multi-row/multi-column MAP detector with 2-D ISI that accounts for feedback information from neighboring bit cells outside the 2-D ISI span. One other embodiment is a 2-D iterative multi-row/column turbo-detector that is a low complexity 2-D detection containing two 1-D optimal detectors operating in orthogonal directions based on a turbo principle. Single row/column and multi-row/column variations are further illustrated in some embodiments. The trellis of the multi-row/column detector is compliant with the span of the 2-D ISI, while the single-row/column version is approximated by a simplified 1-D MAP trellis with much lower complexity.

[0013] Considering the detection of an M×N equiprobable 2-D independent and identically distributed (i.i.d.) binary signal x with elements x(k,l)ε{−1, +1} from received image y with elements
y(m,n)=g(m,n)+w(m,n)  (1)

[0014] where g(m, n) is the 2-D convolution, defined as

[0015] $\begin{array}{cc}g\left(m,n\right)=\sum _k\sum _{l}h\left(m-k,n-l\right)x\left(k,l\right)& \left(2\right)\end{array}$

[0016] In the above equations h(k, l) are the elements of a 2-D finite impulse response/2-D blurring mask and w(m, n) are zero mean independent and identically distributed i.i.d. Gaussian random variables (r.v.s). The double sum is computed over the support of h(m−k, n−l):S(m, n)=(k, l):h(m−k,n−l)≠0. The discrete model in (1) and (2) is applicable to many 2-D ISI channels post front-end signal processing after dealing with channel/media distortions and whitening the media noise.

[0017] FIG. 2, which includes FIGS. 2(a)-(d), shows a mask for a 2-D channel, according to one embodiment. A generalized rectangular-shaped mask is shown in FIG. 2(a). The coefficients in the horizontal direction, i.e. [β_−K1, . . . , β₋₁, 1, β₁, . . . , β_K1] denote horizontal ISI; and the coefficients in the vertical direction, i.e. [α_−K2, . . . , α₋₁, 1, α₁, . . . , α_K2] denote vertical ISI. The size of this mask is (2K₂+1)×(2K₁+1). The coefficients with negative indices denote the causal part (i.e. the pre-cursor ISI); while the positive indices denote the anti-causal part (i.e. the post-cursor ISI). FIG. 2(b) shows the state definition and states transition (the previous state S_j-1=s′ and the current state S_j=s) of the MAP trellis, ‘h’ denotes the horizontal direction and ‘v’ denotes the vertical direction. FIG. 2(c) shows the expectation computation for sample y_m,n from received vector y_i,j with i−K₂≦m<i and n=j−1. Lastly, FIG. 2(d) shows expectation computation from sample y_m,n from received vector y_i,j with i<m≦i+K₂ and n=j−1.

[0018] According to one embodiment, the shape of the 2-D mask may be selected so as to emphasize ISI contributions of adjacent pixels in the orthogonal directions over adjacent pixels in the diagonal directions. A ‘pixel’, as referred to herein, is a 2-D bit cell related to a 2-D sector or a bit cell in shingled magnetic recording, unlike the term “pixel” as used in cameras and imaging. Practical 2-D ISI channels in recording systems may be represented by the ‘band-aid’ shape mask shown in FIGS. 2(a), (b) and (c), according to one embodiment. The mask, however, may be selected to have a shape that emphasizes ISI contributions of adjacent pixels in the radial directions (for example, in hexagonal ISI due to hyper track recording in bit patterned media). In practice, the span of interference in each orthogonal direction i.e., (K₁ and K₂) is small. Diagonal interference may be sufficiently small as to be negligible. Therefore, as shown in FIGS. 2(a), (b) and (c), the 2-D ISI mask may be selected herein with zero coefficients along the diagonals. However, it is to be understood that the coefficients along the diagonals may be non-zero to account for non-zero diagonal interference without departing from the scope of the embodiments disclosed herein

[0019] As in the conventional BCJR algorithm described in L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inform. Theory., vol. 20, pp. 284-287, March 1974), scans based on the forward-backward procedure may be carried out. In one embodiment, to compute the received image y, a boundary of −1 pixels is assumed around x; the detector uses this boundary condition so that the MAP trellis can begin and end in an ‘all −1’ state as demonstrated in Bahl et al., in which ‘−1’ is the bi-polar mapping of an all zero logical state.

[0020] For the generalized 2-D mask shown in FIG. 2(a), given the trellis state
S_j=s[s_−K2,v, . . . ,s_−1,v,s_1,v, . . . ,s_+K2,v,s₀,s_−K1,h, . . . ,s_−1,h,s_1,h, . . . ,s_+K1,h],  (3)

[0021] the input vector
u_i,j=[u_i−K2,j,u_i−K2+1,j, . . . ,u_i−1,j,u_i,j+K1,u_i+1,j, . . . ,u_i+K2−1,j,u_i+K2,j],  (4)
and the received vector sequence Z⁽ⁱ⁾{y_i,j}_1≦j≦N, where the vector y_i,j is the local received samples for trellis stage j at ith row, defined as:
y_i,j=[y_i−k2,j−1,y_{i−k2+1,j−1}, . . . ,y_i−1,j−1,y_i,j,y_+1,j−1, . . . ,y_{i+K2−1,j−1},y_i+K2,j−1],  (5)

[0022] and

[0023] ${\lambda }_{i,j}^{{\underset{\_}{u}}_{i,j}}\left(s\right)$

[0024] is defined as

[0025] $\begin{array}{cc}{\lambda }_{i,j}^{{\underset{\_}{u}}_{i,j}}\left(s\right)\stackrel{\Delta }{=}P\left({\underset{\_}{u}}_{i,j},S_j=s,{\underset{\_}{Z}}^{\left(i\right)}\right).& \left(6\right)\end{array}$

[0026] The a-posteriori probability may now be computed for this multi-row detector as

[0027] $\begin{array}{cc}P\left({\underset{\_}{u}}_{i,j}|{\underset{\_}{z}}^{\left(i\right)}\right)=\sum _s{\lambda }_{i,j}^{{\underset{\_}{u}}_{i,j}}\left(s\right)/P({\underset{\_}{Z}}^{\left(i\right)},& \left(7\right)\end{array}$

[0028] using a modified BCJR algorithm.

[0029] The following are defined:
α_i,j(s)=P(S_j=s,{y_i,a}_1≦a≦j),
β_i,j(S)=P({y_i,a}_j+1≦a≦N|S_j=s),
γ_i,j(s′,s)=P(S_j=s,y_i,j|S_j−1=s′);  (8)
the state transition probability γ may be computed at every stage along the trellis, and after all the γ's are available, the α's and β's may be updated based on the following equations using the forward-backward recursion,

[0030] $\begin{array}{cc}{\alpha }_{i,j}\left(s\right)=\sum _z^{\prime }{\alpha }_{i,j-1}\left(s^{\prime }\right)Y_{i,j}\left(s^{\prime },s\right),& \left(9\right)\\ {\beta }_{i,j-1}\left(s^{\prime }\right)=\sum _z{\beta }_{i,j}\left(s\right)Y_{i,j}\left(s^{\prime },s\right),& \left(10\right)\end{array}$

[0031] After all the α's, δ's and γ's become available, the y probability in equation (6) may be computed as,

[0032] $\begin{array}{cc}{\lambda }_{i,j}^{{\underset{\_}{u}}_{i,j}}=\sum _s^{\prime }{a}_{i,j-1}\left(s^{\prime }\right)Y_{i,j}\left(s^{\prime },s\right){\beta }_{i,j}\left(s\right)& \left(11\right)\end{array}$

[0033] To estimate the pixel located at (i, j+K₁) from the λ's, the λ's may be marginalized over all the other pixels in the input vector u_i,j as,

[0034] $\begin{array}{cc}{\lambda }_{i,j-K_1}^{u_{i,j}}\left(S_j-K_1\right)=\sum _{{}_{{\underset{\_}{u}}_{i,j-K_1\backslash u_{i,j}}}}{\lambda }_{i,j-K_1}^{{\underset{\_}{u}}_{i,j-K_1}}\left(S_{j-K_1}\right).& \left(12\right)\end{array}$

[0035] The delay of K₁ of the index accounts for the ISI shape and boundary conditions.

[0036] The output pixel LLR may be computed as:

[0037] $\begin{array}{cc}L\left(i,j\right)=\ln \left(\frac{\sum _{S_{j-K_1}}{\lambda }_{i,j-K_1}^{u_{i,j}=+1}\left(S_{j-K_1}\right)}{\sum _{S_{j-K_1}}{\lambda }_{i,j-K_1}^{u_{i,j}=-1}\left(S_{j-K_1}\right)}\right).& \left(13\right)\end{array}$

[0038] If L(i, j)>0 pixel (i, j) may be detected as +1; otherwise pixel (i, j) may be detected as −1.

[0039] The conditional probability γ_i,j (s′, s) is decomposed to the product of two other conditional probabilities based on Bayesian rule:

[0040] $\begin{array}{cc}\begin{array}{c}\gamma i,j=\left(s^{\prime },s\right)=P\left(S_j=s,{\underset{\_}{y}}_{i,j}|S_{j-1}=s^{\prime }\right)\\ =P\left({\underset{\_}{y}}_{i,j}|S_j=s,S_{j-1}=s^{\prime }\right)P\left(S_j=s|S_{j-1}=s^{\prime }\right)\\ =P\left({\underset{\_}{y}}_{i,j}|S_j=s,S_{j-1}=s^{\prime }\right)P\left({\underset{\_}{u}}_{i,j}\right).\end{array}& \left(14\right)\end{array}$

[0041] The last equality holds in (14), because the input is the branch connecting two adjacent stages, and this vector determines the next state given the current state. For the non-iterative detection embodiment, there is no a-priori information. It is assumed in that case that all the input pixels are equally likely when computing P(u_i,j) in equation (14). Since the first conditional probability in the product of (14) is Gaussian distributed, it may be computed it as,

[0042] $\begin{array}{cc}\begin{array}{c}P\left({\underset{\_}{y}}_{i,j}❘S_j=s,S_{j-1}=s^{\prime }\right)\\ \approx P\left(y_{i,j}|S_j=s,S_{j-1}=s^{\prime }\right)\\ \prod _{m=-K_2,m\ne 0}^{K_2}P\left(y_{i+m,j-1}|S_j=s,S_{j-1}=s^{\prime }\right)\\ =\frac{1}{\sqrt{2\pi }{\sigma }_{\omega }}\exp \left(-\frac{{\left(y_{i,j}-\stackrel{\_}{y_{i,j}}\right)}^2}{2{\sigma }_{\omega }^2}\right)\\ \prod _{m=-K_2,m\ne 0}^{K_2}\frac{1}{\sqrt{2\pi }{\sigma }_{\omega }}\exp \left(-\frac{{\left(y_{i+m,j-1}-\stackrel{\_}{y_{i+m,j-1}}\right)}^2}{2{\sigma }_{\omega }^2}\right).\end{array}& \left(15\right)\end{array}$

[0043] In one embodiment, in the second step of equation (15), it is assumed that all the conditional probabilities are statistically independent of each other. This may not be is true for larger ISI spans, but this assumption is a reasonable practical approximation to realize the algorithm. For the conditional probabilities in equation (15), the expectations are computed based on the index (m, n) of the received sample y and the components of the 2D mask shown in FIG. 2(a). Given m=i and n=j, the expectation is,

[0044] $\begin{array}{cc}\stackrel{\_}{y_{m,n}}=S_0+\prod _{p=-K_2,p\ne 0}^{K_2}{\alpha }_p{s}_{p,\upsilon }+\prod _{p=-K_1,p\ne 0}^{K_1}{\beta }_p{s}_{p,h}.& \left(16\right)\end{array}$

[0045] Given i−K₂≦m<i and n=j−1, the expectation is,

[0046] $\begin{array}{cc}\stackrel{\_}{y_{m,n}}=s_{m,\upsilon }^{\prime }+\sum _{p=1}^{K_2}{\alpha }_p{s}_{m+p,\upsilon }^{\prime }+\sum _{p=1}^{K_2+m-i}{\alpha }_{-p}{s}_{m-p,\upsilon }^{\prime }+\prod _{p=K_2+m-i+1}^{K_2}{\alpha }_{-p}{\omega }_{p-K_2-m+i,\upsilon }+s_{m,\upsilon }{\beta }_1+\sum _{p=1}^{K_1}{\beta }_{-p}{\omega }_{-p,h}+\sum _{p=1}^{K_2}{\beta }_p{\omega }_{p,h}.& \left(17\right)\end{array}$
There are i−m feedback pixels in vertical direction, (i.e., ω_1,v through ω_i-m,v), and 2K₁−1 feedback pixels in the horizontal direction, (i.e., ω_2,h through ω_K1,h and ω_−K1,h through ω_−1,h), as also shown in FIG. 2(c).

[0047] Given i<m≦i+K₂ and n=j−1, the expectation is,

[0048] $\begin{array}{cc}\stackrel{\_}{y_{m,n}}=s_{m,\upsilon }^{\prime }+\sum _{p=1}^{K_2}{\alpha }_p{s}_{m-p,\upsilon }^{\prime }+\sum _{p=1}^{K_2-m+i}{\alpha }_p{s}_{m+p,\upsilon }^{\prime }+\prod _{p=K_2-m+i+1}^{K_2}{\alpha }_p{\omega }_{p-K_2+m-i,\upsilon }+s_{m,\upsilon }{\beta }_1+\sum _{p=1}^{K_1}{\beta }_{-p}{\omega }_{-p,h}+\sum _{p=1}^{K_2}{\beta }_p{\omega }_{p,h}.& \left(18\right)\end{array}$

[0049] There are m−i feedback pixels in vertical direction, (i.e., ω_1,v through w and 2K₁−1 feedback pixels in the horizontal direction, (i.e., ω_2,h through ω_K1,h and ω_−K1,h through ω_−1,h), as also shown in FIG. 2(d).

[0050] In one embodiment, the total number of the feedback pixels in the vertical direction is |i−m| which will change with the index m; while the total number of feedback pixels in the horizontal direction is a constant 2K₁−1.

[0051] FIG. 3 shows the states, inputs and inner product definition for a simplified MAP trellis on a single row, according to one embodiment. In FIG. 3, S_j={S0,S₁} and S_j−1={s′0,s′₁}. For a 3×3 mask as shown in FIG. 3, there are 5 state pixels contributing to 32 states configuration and 3 input pixels contributing to 8 branches in/out from one state of the trellis to the other. In FIG. 3, s′ denotes the prior state and s denotes the next state. It is to be understood that other mask sizes such as, for example, 5×5, may be selected, albeit with higher complexity.

[0052] FIG. 4 shows the states, inputs and inner product definition for a MAP trellis on multi-rows, according to one embodiment. The shape of the mask may be dependent on the layout of the tracks of the disk(s) 102. For instance, in hyper-track recording, the shape of the mask may be hexagonal, consistent with the written tracks. In the case of centered writing, the mask shape may be rectangular. According to one embodiment, the mask may be selected, for ISI considerations for data stored on adjacent tracks of a disk drive, to be a 2-D ‘band-aid’ or “cross-shape” type of mask, as shown in FIG. 4. According to one embodiment, the mask may be selected to have a hexagonal shape. The ISI may be chosen as a symmetric response for illustration purposes. This however does not restrict the embodiment, which may be extended to a more general case.

[0053] $h=\left[\begin{array}{ccc}0& \alpha & 0\\ \beta & 1& \beta \\ 0& \alpha & 0\end{array}\right]$

[0054] The selection of the mask may include selecting a shape (through selection of the channel coefficients) so as to emphasize ISI contributions of adjacent pixels in an orthogonal direction over adjacent pixels in a diagonal direction. Accordingly, the channel coefficients at the corners of the channel model h above may be selected to be zero. Since the ISI is spanning 3 rows, a local span of 3 rows and 3 columns may be considered in one embodiment. In general, a 2-D trellis must span over the entire 2-D signal span and the forward backward technique must be computed at each point over the entire signal span. Thus the worst case complexity is N⁴ assuming an N×N size 2-D data sector.

[0055] Let {y_i,j} denote the set of received samples. In reality for TDMR, these will be equalized samples post front-end signal processing. A ‘pixel’, as referred to herein, is a 2-D bit cell related to a 2-D sector or a bit cell in a shingled setup, unlike the term “pixel” as used in cameras and imaging. The current state is defined as the 2-D “band-aid” type shape shown in thick lines in FIG. 4. In FIG. 4, the previous state is shown as ‘o’ circles. The overlap between the states is 2 pixels horizontally. The inputs will be the three elements [s₀s₃s₄] that correspond to the bits at locations [(i,j+1)(i−1,j)(i+1,j)] respectively. The pixels [w₀w₁] from locations [(i−1,j−2)(i−2,j−1)] influence the pixel state at location (i−1,j−1). Similarly pixels/bits [w₂w₃] from locations [(i+1,j−2)(i+2,j−1)] influence the pixel state at location (i+1,j−1). These pixels can be considered as feedback pixels. When the engine is run, usually feedback pixels values are unknown. Hence the stand-alone non-iterative detector estimates the value of the pixel at locations (i−1,j−1) and (i+1,j−1) by marginalizing over the pixels around its vicinity that are outside the trellis. A boundary of all zero pixels bi-polar mapped to ‘−1’ may be used so that trellis warm up and closure is appropriately handled.

[0056] FIG. 5 is a flowchart for a computer-implemented method of decoding data written over a plurality of tracks of a disk of a hard disk drive, according to one embodiment. As show therein, FIG. 5 includes a block B51 that calls for, as shown in FIGS. 2(a) through 2(d), selecting a mask configured to account for ISI. In one embodiment, the mask includes selected channel coefficients and defines a trellis that defines a plurality of states.

[0057] As shown in Block B52, a signal is then received, and equalized samples are generated from the received signal. That is, the received signal may correspond to an input pixel of a current state from each of the plurality of tracks. The received signal may be analog-to-digital converted, filtered through a Finite Impulse Response (FIR) filter and equalized to generate the equalized samples.

[0058] Transition branch probabilities (from a current state s′ to a next state s) may then be computed for each input vector based on a Gaussian noise distribution using the equalized samples, ideal samples and a priori probabilities of the input vector, as shown at Block B53. According to one embodiment, the ideal samples may be computed by convolving the input vector with a 2-D partial response target. Block B54 calls for computing forward and backward probabilities, according to equations (8), (9) and (10) above, via 2-D recursions using the computed transition branch probabilities for each of the plurality of states of the trellis. Each iteration of the recursion may utilize the results from the last recursion, as set forth in equations (9) and (10) above. As shown in block B55, the computed forward probabilities, backward probabilities and the transition branch probabilities may then be combined, to generate a-posteriori probabilities for the input vector, as defined in equation (11) above. As shown at block B56 and as defined in equation (12) above, the a-posteriori probabilities may then be marginalized over values of neighboring pixels to generate an a-posteriori probability for a pixel of the input vector in a given state. Finally, as called for by block B57 and as defined at equation (13), the pixel may be decoded as a first logical state (e.g., 0 or 1 in a binary system) or a second logical state (e.g., 0 or 1 in a binary system) from the marginalized a-posteriori probabilities.

[0059] According to one embodiment, the decoding in block B57 may be carried out by summing each of the plurality of states of the trellis corresponding to the pixel assuming a first value (such as −1, for example) and summing each of the plurality of states of the trellis corresponding to the pixel assuming a second value that is of opposite polarity as the first value (such as +1, for example). A ratio may then be calculated of a sum over most or all the states of the marginalized a-posteriori probabilities corresponding to pixels that are of the first value over a sum of most or all states corresponding to pixels that are of the second value, to obtain an output pixel log likelihood ratio (LLR). From the output pixel LLR (equation (13) above), the input pixel's value may be decoded as a first logical state if the output pixel LLR is greater than 0 and as a second logical state if the output pixel LLR is less than or equal to 0. For example, if the output pixel LLR of equation (13) evaluates to zero, the pixel may be decoded as having a first logical value (0, for example) and if equation (13) evaluates to a value that is greater than zero, the pixel may be decoded as having a second logical value (such as 1, for example).

[0060] FIG. 6 is a block diagram of a decoder configured to decode data written over a plurality of tracks of a disk of a hard disk drive, according to one embodiment. As shown therein, the decoder 502 may include a memory 506 and a processor 504, the processor 504 being coupled to the memory 506. According to one embodiment, the processor 504 may be any combination of hardware, software, and/or firmware that together execute the methods shown and described relative to FIG. 5, as well as 1-4 and 6-9.

[0061] Practical channels usually have small ISI span. For purposes of computational illustration, in one embodiment, a simple 2-D mask is chosen such that h=[0α0;β1β; 0α0] of size 3×3, and assumed to be symmetric, as shown in FIGS. 2 and 3. For a trellis based on a 3×3 mask h, there are 5 state pixels (i.e., s₀ through s₄ in FIG. 4), contributing to 32 states configuration and 3 input pixels. The 3 input pixels lead to 8 branches coming into/going out from one state. Also, there are 4 feedback pixels (ω₀, w₁, w₂, w₃), which may be used to compute the state transition probability in the BCJR process. The a-priori information for both the input pixels and the feedback pixels come is from the previous detector. With no feedback, they can be assumed to be zero a-priori. With feedback, extrinsic information from the previous detector will be set as feedback, as discussed hereunder.

[0062] The branch metrics may be defined as the squared Euclidean distances (SEDs) between the branch output vectors and the received pixel vectors y_i,j[y_i−1,j−1, y_i,j, y_i+1,j−1]. As shown in FIG. 4, y_i,j corresponds to the position of s₁ or s′₀, while y_i−1,j−1 corresponds to the position of s′₃ and y_i-1,j+1 corresponds to s′₄.

[0063] For the 3×3 mask shown in FIG. 4, equation (15) may be modified as

[0064] $\begin{array}{cc}P\left({\underset{\_}{y}}_{i,j}❘S_j=s,S_{j-1}=s^{\prime }\right)=\{\begin{array}{c}\mathrm{For}\mathrm{simplified}\mathrm{MAP}\mathrm{trellis}\\ \sum _{{\omega }_0,{\omega }_1}P\left({\omega }_0\right)P\left({\omega }_1\right)P\left(y_{i,j}❘s,s^{\prime }\stackrel{\_}{y_{i,j}}\left({\omega }_0,{\omega }_1\right)\right)\\ \mathrm{For}\mathrm{MAP}\mathrm{trellis}\left(\mathrm{three}\text{-}\mathrm{rows}\mathrm{version}\right)\\ P\left(y_{i,j}❘s,s^{\prime }\stackrel{\_}{y_{i,j}}\right)\times [\sum _{{\omega }_0,{\omega }_1}P\left({\omega }_0\right)P\left({\omega }_1\right)\\ P\left(y_{i-1,j-1}❘s,s^{\prime },\stackrel{\_}{y_{i-1,j-1}}\left({\omega }_0,{\omega }_1\right)\right)]\times \\ \left[\sum _{{\omega }_2{\mathrm{m\omega }}_3}P\left({\omega }_2\right)P\left({\omega }_3\right)P\left(y_{i+1,j-1}❘s,s^{\prime },\stackrel{\_}{y_{i+1,j-1}}\left({\omega }_2,{\omega }_3\right)\right)\right].\end{array}& \left(19\right)\end{array}$

[0065] In equation (19), the expectations of the terms within the Gaussian conditional probabilities are computed based on the states definitions, the feedback pixels for the corresponding trellis and the 3×3 mask h, as shown in FIG. 4 as follows:
y_i,j(ω₀,ω₁)=s₁α(ω₀+ω₁+β(s′₁+s₀);
y_i,j=s₁+α(s₃+s₄)+β(s₀+s₂;
y_i+1,j−1(ω₀,ω₁)=s′₃+α(ω₁+s′₁)+β(ω₀+s₃);
y_i+1,j−1(ω₂,ω₃)=s′₄+α(ω₃+s′₁+β(ω₂+s₄).  (20)

[0066] All the Gaussian probabilities above have the same variance.

[0067] The multi-row trellis shown in equation (19) processes three adjacent data tracks simultaneously. In the computation of P(y_i,j|S_j=s, S_j−1=s′), y_i,j may be defined as y_i,j=[y_i−1,j−1, y_i,j, y_i+1,j−1]. For convenience, this non-iterative 2-D detection embodiment that processes three adjacent data tracks simultaneously is denoted ‘algorithm B’.

[0068] However, for the ‘one-row version’ embodiment that only processes one single data track, the trellis definition in FIG. 4 will only keep the central three rows, and all the feedback pixels will disappear, and only the expectation of is needed to compute is the state transition probability. The computation in equation (19) may then be modified as:

[0069] $\begin{array}{cc}P\left(y_{i,j}❘S_j=s,S_{j-1}=s^{\prime }\right)=\frac{1}{\sqrt{2\pi }{\sigma }_{\omega }}\exp \left(-\frac{{\left(y_{i,j}-\stackrel{\_}{y_{i,j}}\right)}^2}{2{\sigma }_{\omega }^2}\right),& \left(21\right)\end{array}$

[0070] where the y_i,j is just the received sample from one single data track, and y_i,j=s₁+α(s₃+s₄)+β(s₀+s₂). For convenience, this non-iterative 2-D detection embodiment that processes a single track is denoted as ‘algorithm A’.

[0071] The relation between the ‘one-row’ version embodiment and ‘three-rows’ version embodiment may be also be generalized to arbitrary 2D ISI channels. In one or more embodiments, the best performance may be obtained by processing R adjacent rows (data tracks) simultaneously, where R=max(2K₁+1, 2K₂+1), but with the highest complexity.

Turbo Based Detection

[0072] One embodiment is based on a 2-D iterative scheme that takes advantage of different error decisions and noise distribution at the output of the row and column detectors. FIG. 7 is a simplified MAP trellis showing a-priori information from a previous detector and a MAP trellis also showing a-priori information from a previous detector, is according to one embodiment. In FIG. 7, the pixels needing the a-priori information, for the simplified MAP trellis of part (a) of FIG. 7, are S_j={s₀, s₁} and ={s′₀, s′₁}, and for the MAP trellis of part (b) of FIG. 7, are S_j={s₀, s₁, s₂, s₃, s₄} and ={s′₀, s′₁, s′₂, s′₃, s′₄}. For a turbo based iterative embodiment, needed is the probability of the input pixel(s) (as part of the trellis), s₀ in part (a) of FIG. 7 and s₀, s₃, s₄ in part (b) of FIG. 7 and the probability of the feedback pixels (outside of the trellis), ω₀,ω₁ in part (a) of FIG. 7 and ω₀ through ω₃ in part (b) of FIG. 7. Scaled extrinsic information coming from the previous detector may be used in the iterative embodiment. When computing the probability of the corresponding pixels using the a-priori information (i.e., the probabilities of all the feedback pixels in equation (19) and P(u_i,j) in equation (14)), it is assumed that the pixels are statistically independent.

[0073] According to one embodiment, to compute the a-priori probability for a specified pixel y_i,j from the incoming extrinsic information of this pixel L_eⁱⁿ (y_i,j), the following equations may be applied:

[0074] $\begin{array}{cc}P\left(y_{i,j}=+1❘y_{\tilde{i},j}\right)=\frac{\exp \left(L_e^{\mathrm{in}}\left(y_{i,j}\right)\right)}{\exp \left(L_e^{\mathrm{in}}\left(y_{i,j}\right)\right)+1};P\left(y_{i,j}=-1❘y_{\tilde{i},j}\right)=\frac{1}{\exp \left(L_e^{\mathrm{in}}\left(y_{i,j}\right)\right)+1}.& \left(22\right)\end{array}$
where y_i,j^˜ denotes the a-priori information on pixel y_i,j. For convenience, the iterative 2-D detection embodiment that computes y's using the equation (19) taking account of the a-priori information for both the feedback pixels and P(u_i,j) is denoted herein ‘algorithm D’ in Table 1 herein below and in FIG. 9. The iterative algorithm using only the a-priori information of the feedback pixels is denoted ‘algorithm C’.

[0075] A state is defined comprising of two adjacent pixels s₀ and s₁ in the row direction as shown in FIG. 3; an input pixel that is the branch connecting two neighboring states determines the next state. To fit into the shape of a local 2-D ISI (the ‘band-aid’ shape), two extra feedback pixels may be added (ω₀, ω₁) besides the pixels comprising of the trellis states and inputs. The state transition probability may be computed using the equation (19). The a-priori information on both the feedback pixels and P(u_i,j) is used. This simplified scheme is referred to as ‘algorithm E’ in Table 1 and FIG. 9.

[0076] FIG. 8 shows a block diagram of an iterative 2-D turbo detector, according to one embodiment. The row detector 702 and the column detector 704 pass soft extrinsic information (LLRs) between each other with LLR scaling on the soft extrinsic information. Accordingly, in an iterative turbo-based detection embodiment, the output pixel LLR (equation (13)) constitutes an output of a row detector 702. According to one embodiment, a column detector may be configured to be similar to the row detector 702, but for processing transposed equalized samples and a transposed mask. The output pixel LLR from the row detector 702 may be converted into first extrinsic LLR that is input to the column detector 704 as a-priori information for the column detector 704. The output pixel LLR output from the column detector 704 may then be converted into second extrinsic LLR that is input back to the row detector 702 as a-priori information for the row detector 702, as shown. Additional iterations may follow the same pattern. According to one embodiment, the output of the row detector 702 may be scaled or weighted by a first weighting factor 706 and the output of the column detector may be scaled or weighted by a second weighting factor 708.

[0077] The scaling process (i.e. weight) on the extrinsic information (LLRs) may be used to avoid quick convergence during iterative detection. The weights δ 706, 708 may be effective to lower the magnitude of the ‘bad’ LLRs with high magnitude in opposite polarity that may propagate into the next detection cycle. The performance tends to converge after several turbo iterations.

[0078] In the turbo embodiment, the log-likelihood ratio L(i, j) may be split into a term that depends on the incoming extrinsic information L_eⁱⁿ (y_i,j) to the current (row or column) detector 702, 704, and a term that does not. Hence, L_eⁱⁿ (y_i,j) may be subtracted from L(i, j) to form the extrinsic information L^out(i, j) that may be passed to the next detector as the extrinsic information,
L_out(i,j)=L(i,j)−L_eⁱⁿ(i,j).  (23)

[0079] The same process may be carried out for one or more of the iterative 2-D detection embodiments disclosed herein.

[0080] Complexity Analysis

[0081] One embodiment is a low complexity 2-D detection algorithms employing 1-D MAP technique operating over rows and columns within a turbo iteration framework to realize a ‘near true 2-D detection’ performance. A size N×N binary source image may be used for complexity test. The length of the trellis within a single row is N. Operating over the entire image with N rows, the data may be processed N×N times. The complexity comparison between different algorithms is summarized in Table 1 below. The comparison unit is ‘per detector per iteration’, since some algorithms employ iterative schemes with more than one detector in a single iteration.

[0082] Simulation Results

[0083] Monte Carlo simulation of the 2-D detection algorithms were carried out and the results thereof compared. All simulations employ a random 64×64 binary source image x(m, n)ε{−1, +1}. All of the images have a boundary corresponding to the mask size, so that the trellis may start and end at an ‘all −1’ state. The Signal-To-Noise Ratio (SNR) may be defined as:

[0084] $\begin{array}{cc}\begin{array}{c}\mathrm{SNR}=10{\log }_{10}\left(\frac{{\mathrm{hx}}^2}{{\sigma }_{\omega }^2}\right)\\ =10{\log }_{10}\left(\frac{\sum _{i,j}{h}^2\left(i,j\right)}{{\sigma }_{\omega }^2}\right)\end{array}& \left(24\right)\end{array}$
where σ_ω^z is the variance of the Gaussian r.v.s ω (m, n) in Equation (2). It is assumed that α=β in the 3×3 mask h, for simulation purposes.

[0085]

TABLE 1
Computational Complexity Comparison
of Different 2-D Detection Algorithms
(with an N × N binary Source Image and 3 × 3 ISI)
	Algorithm	Algorithm	Algorithm	Algorithm
Algorithm	E	A	B	D
add/subtract	212 · N2	4384 · N2	10016 · N2	14368 · N2
multiply/divide	281 · N2	5889 · N2	15105 · N2	19457 · N2
exp/log	177 · N2	257 · N2	2305 · N2	11009 · N2

[0086] Iterative algorithms C and D employ a 5-iteration scheme with a weight σ=0.8 for extrinsic information scaling; while algorithm E uses a 10-iteration scheme with weight σ=0.5. The performance of the algorithms converges; i.e., no more significant SNR gain, after these numbers of iterations discussed herein. The three-row non-iterative version ‘algorithm B’ performs much better than the one-row version ‘algorithm is A’, since the state transition probability in BCJR algorithm is computed more accurately (i.e. more contributing terms dealing with ISI rather than in the single case). Algorithms C and D spanning multi-rows/columns perform better than algorithm E with simplified trellis because handling multiple row/columns have better 2-D ISI cancellation than a single-row/column iterative detector.

[0087] FIG. 9 shows the results of a Monte Carlo simulation for different detection embodiments. The SNR, in dB is shown on the abscissa, while the Bit Error Rate (BER) is shown on the ordinate. As shown, algorithm E, at BER 10⁻⁶, is just within 0.5 dB of the algorithms C and D. As also shown in FIG. 9, for algorithm C and D, at BER 10⁻⁶, the iterative algorithm is more than 2 dB better than the non-iterative one.

[0088] Algorithm E in FIG. 9 has undergone 10 iterations in total. Even after multiplying the complexity numbers in Table I for algorithm E by a factor of 10, the results are still smaller than the numbers for algorithms A and B. Algorithm E is 0.3% as complex as algorithm D with 5 iterations, but with a SNR loss of about 0.5 dB at BER 10⁻⁶ as shown in FIG. 9. Thus, algorithm E can be a good choice considering complexity and performance balance.

[0089] While certain embodiments of the inventions have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the inventions. Indeed, the novel methods, devices and systems described herein may be embodied in a variety of other forms. Furthermore, various omissions, substitutions and changes in the form of the detection methods and detectors described and shown herein may be made without departing from the spirit of the inventions. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the inventions. For example, those skilled in the art will appreciate that in various embodiments, the actual structures (such as, for example,) may differ from those shown in the figures. Depending on the embodiment, certain of the steps described and shown herein may be removed, while others may be added. Also, the features and attributes of the specific embodiments disclosed above may be combined in different ways to form additional embodiments, all of which fall within the scope of the present disclosure. Although the present disclosure provides certain preferred embodiments and applications, other embodiments that are apparent to those of ordinary skill in the art, including embodiments which do not provide all of the features and advantages set forth herein, are also within the scope of this disclosure. Accordingly, the scope of the present disclosure is intended to be defined only by reference to the appended claims.