Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain
137
0
0.0
(
0
)
Added by
Robin Scheibler
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an $N$ dimensional signal with a $K$-sparse WHT, where $N$ is a power of two and $K = O(N^alpha)$, scales sub-linearly in $N$ for some $0 < alpha < 1$. Assuming a random support model for the non-zero transform domain components, the algorithm reconstructs the WHT of the signal with a sample complexity $O(K log_2(frac{N}{K}))$, a computational complexity $O(Klog_2(K)log_2(frac{N}{K}))$ and with a very high probability asymptotically tending to 1. The approach is based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time domain signal, one can induce a suitable aliasing pattern in the transform domain. By treating the aliasing patterns as parity-check constraints and borrowing ideas from erasure correcting sparse-graph codes, the recovery of the non-zero spectral values has been formulated as a belief propagation (BP) algorithm (peeling decoding) over a sparse-graph code for the binary erasure channel (BEC). Tools from coding theory are used to analyze the asymptotic performance of the algorithm in the very sparse ($alphain(0,frac{1}{3}]$) and the less sparse ($alphain(frac{1}{3},1)$) regime.
rate research
Read More
In this paper we propose efficient decoding techniques to significantly improve the error-correction performance of fast successive-cancellation (FSC) and FSC list (FSCL) decoding algorithms for short low-order Reed-Muller (RM) codes. In particular, we first integrate Fast Hadamard Transform (FHT) into FSC (FHT-FSC) and FSCL (FHT-FSCL) decoding algorithms to optimally decode the first-order RM subcodes. We then utilize the rich permutation group of RM codes by independently running the FHT-FSC and the FHT-FSCL decoders on a list of random bit-index permutations of the codes. The simulation results show that the error-correction performance of the FHT-FSC decoders on a list of $L$ random code permutations outperforms that of the FSCL decoder with list size $L$, while requiring lower memory requirement and computational complexity for various configurations of the RM codes. In addition, when compared with the state-of-the-art recursive projection-aggregation (RPA) decoding, the permuted FHT-FSCL decoder can obtain a similar error probability for the RM codes of lengths $128$, $256$, and $512$ at various code rates, while requiring several orders of magnitude lower computational complexity.
In this paper, a discrete LCT (DLCT) irrelevant to the sampling periods and without oversampling operation is developed. This DLCT is based on the well-known CM-CC-CM decomposition, that is, implemented by two discrete chirp multiplications (CMs) and one discrete chirp convolution (CC). This decomposition doesnt use any scaling operation which will change the sampling period or cause the interpolation error. Compared with previous works, DLCT calculated by direct summation and DLCT based on center discrete dilated Hermite functions (CDDHFs), the proposed method implemented by FFTs has much lower computational complexity. The relation between the proposed DLCT and the continuous LCT is also derived to approximate the samples of the continuous LCT. Simulation results show that the proposed method somewhat outperforms the CDDHFs-based method in the approximation accuracy. Besides, the proposed method has approximate additivity property with error as small as the CDDHFs-based method. Most importantly, the proposed method has perfect reversibility, which doesnt hold in many existing DLCTs. With this property, it is unnecessary to develop the inverse DLCT additionally because it can be replaced by the forward DLCT.
Generalized analytic signal associated with the linear canonical transform (LCT) was proposed recently by Fu and Li [Generalized Analytic Signal Associated With Linear Canonical Transform, Opt. Commun., vol. 281, pp. 1468-1472, 2008]. However, most real signals, especially for baseband real signals, cannot be perfectly recovered from their generalized analytic signals. Therefore, in this paper, the conventional Hilbert transform (HT) and analytic signal associated with the LCT are concerned. To transform a real signal into the LCT of its HT, two integral transforms (i.e., the HT and LCT) are required. The goal of this paper is to simplify cascades of multiple integral transforms, which may be the HT, analytic signal, LCT or inverse LCT. The proposed transforms can reduce the complexity when realizing the relationships among the following six kinds of signals: a real signal, its HT and analytic signal, and the LCT of these three signals. Most importantly, all the proposed transforms are reversible and undistorted. Using the proposed transforms, several signal processing applications are discussed and show the advantages and flexibility over simply using the analytic signal or the LCT.
Orthogonal time frequency space (OTFS) modulation can effectively convert a doubly dispersive channel into an almost non-fading channel in the delay-Doppler domain. However, one critical issue for OTFS is the very high complexity of equalizers. In this letter, we first reveal the doubly block circulant feature of OTFS channel represented in the delay-Doppler domain. By exploiting this unique feature, we further propose zero-forcing (ZF) and minimum mean squared error (MMSE) equalizers that can be efficiently implemented with the two-dimensional fast Fourier transform. The complexity of our proposed equalizers is gracefully reduced from $mathcal{O}left(left(NMright)^{3}right)$ to $mathcal{O}left(NMmathrm{log_{2}}left(NMright)right)$, where $N$ and $M$ are the number of OTFS symbols and subcarriers, respectively. Analysis and simulation results show that compared with other existing linear equalizers for OTFS, our proposed linear equalizers enjoy a much lower computational complexity without any performance loss.
We present the generalized iterative residual fitting (IRF) for the computation of the spherical harmonic transform (SHT) of band-limited signals on the sphere. The proposed method is based on the partitioning of the subspace of band-limited signals into orthogonal subspaces. There exist sampling schemes on the sphere which support accurate computation of SHT. However, there are applications where samples~(or measurements) are not taken over the predefined grid due to nature of the signal and/or acquisition set-up. To support such applications, the proposed IRF method enables accurate computation of SHTs of signals with randomly distributed sufficient number of samples. In order to improve the accuracy of the computation of the SHT, we also present the so-called multi-pass IRF which adds multiple iterative passes to the IRF. We analyse the multi-pass IRF for different sampling schemes and for different size partitions. Furthermore, we conduct numerical experiments to illustrate that the multi-pass IRF allows sufficiently accurate computation of SHTs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
