While vision-language foundation models (VLMs) achieve remarkable performance when fine-tuned on downstream in-distribution (ID) data, this process compromises their generalization ability on out-of-distribution (OOD) data that deviate from the downstream tasks due to overfitting. To address this, we propose ProLoG, a new adaptation method that effectively fine-tunes VLMs on downstream tasks while achieving high OOD performance. Specifically, we design a unique integration of prompt tuning and LoRA, offering a robust hybrid platform to improve performance. During training, we propose an augmentation-based regularization loss that enhances the generalization of our hybrid network by using augmented image features aligned with LLM-generated texts containing key attributes of each class. By leveraging our hybrid design, we also introduce an adaptive inference strategy that flexibly applies trained prompts and LoRA based on a task similarity score to effectively handle both ID and OOD data. Experimental results demonstrate that our proposed method outperforms existing works on various datasets, confirming its advantages.

In response to the increasing demand for tackling out-of-domain (OOD) scenarios, test-time adaptation (TTA) has garnered significant research attention in recent years. To adapt a source pre-trained model to target samples without getting access to their labels, existing approaches have typically employed entropy minimization (EM) loss as a primary objective function. In this paper, we propose an adaptive energy alignment (AEA) solution that achieves fast online TTA. We start from the re-interpretation of the EM loss by decomposing it into two energy-based terms with conflicting roles, showing that the EM loss can potentially hinder the assertive model adaptation. Our AEA addresses this challenge by strategically reducing the energy gap between the source and target domains during TTA, aiming to effectively align the target domain with the source domains and thus to accelerate adaptation. We specifically propose two novel strategies, each contributing a necessary component for TTA: (i) aligning the energy level of each target sample with the energy zone of the source domain that the pre-trained model is already familiar with, and (ii) precisely guiding the direction of the energy alignment by matching the class-wise correlations between the source and target domains. Our approach demonstrates its effectiveness on various domain shift datasets including CIFAR10-C, CIFAR100-C, and TinyImageNet-C.

Research interests in the robustness of deep neural networks against domain shifts have been rapidly increasing in recent years. Most existing works, however, focus on improving the accuracy of the model, not the calibration performance which is another important requirement for trustworthy AI systems. Temperature scaling (TS), an accuracy-preserving post-hoc calibration method, has been proven to be effective in in-domain settings, but not in out-of-domain (OOD) due to the difficulty in obtaining a validation set for the unseen domain beforehand. In this paper, we propose consistency-guided temperature scaling (CTS), a new temperature scaling strategy that can significantly enhance the OOD calibration performance by providing mutual supervision among data samples in the source domains. Motivated by our observation that over-confidence stemming from inconsistent sample predictions is the main obstacle to OOD calibration, we propose to guide the scaling process by taking consistencies into account in terms of two different aspects - style and content - which are the key components that can well-represent data samples in multi-domain settings. Experimental results demonstrate that our proposed strategy outperforms existing works, achieving superior OOD calibration performance on various datasets. This can be accomplished by employing only the source domains without compromising accuracy, making our scheme directly applicable to various trustworthy AI systems.

Handling the substantial communication burden in federated learning (FL) still remains a significant challenge. Although recent studies have attempted to compress the local gradients to address this issue, they typically perform compression only within the original parameter space, which may potentially limit the fundamental compression rate of the gradient. In this paper, instead of restricting our scope to a fixed traditional space, we consider an alternative space that provides an improved compressibility of the gradient. To this end, we utilize the structures of input activation and output gradient in designing our mapping function to a new space, which enables *lossless gradient sparsification*, i.e., mapping the gradient to our new space induces a greater number of *near-zero* elements without any loss of information. In light of this attribute, employing sparsification-based compressors in our new space allows for more aggressive compression with minimal information loss than the baselines. More surprisingly, our model even reaches higher accuracies than the full gradient uploading strategy in some cases, an extra benefit for utilizing the new space. We also theoretically confirm that our approach does not alter the existing, best known convergence rate of FL thanks to the orthogonal transformation properties of our mapping.

The demand for intelligent services at the network edge has introduced several research challenges. One is the need for a machine learning architecture that achieves personalization (to individual clients) and generalization (to unseen data) properties concurrently across different applications. Another is the need for an inference strategy that can satisfy network resource and latency constraints during testing-time. Existing techniques in federated learning have encountered a steep trade-off between personalization and generalization, and have not explicitly considered the resource requirements during the inference-stage. In this paper, we propose SplitGP, a joint edge-AI training and inference strategy that simultaneously captures generalization/personalization for efficient inference across resource-constrained clients. The training process of SplitGP is based on federated split learning, with the key idea of optimizing the client-side model to have personalization capability tailored to its main task, while training the server-side model to have generalization capability for handling out-of-distribution tasks. During testing-time, each client selectively offloads inference tasks to the server based on the uncertainty threshold tunable based on network resource availability. Through formal convergence analysis and inference time analysis, we provide guidelines on the selection of key meta-parameters in SplitGP. Experimental results confirm the advantage of SplitGP over existing baselines.

As the size of a model increases, making predictions using deep neural networks (DNNs) is becoming more computationally expensive. Multi-exit neural network is one promising solution that can flexibly make anytime predictions via early exits, depending on the current test-time budget which may vary over time in practice (e.g., self-driving cars with dynamically changing speeds). However, the prediction performance at the earlier exits is generally much lower than the final exit, which becomes a critical issue in low-latency applications having a tight test-time budget. Compared to the previous works where each block is optimized to minimize the losses of all exits simultaneously, in this work, we propose a new method for training multi-exit neural networks by strategically imposing different objectives on individual blocks. The proposed idea based on grouping and overlapping strategies improves the prediction performance at the earlier exits while not degrading the performance of later ones, making our scheme to be more suitable for low-latency applications. Extensive experimental results on both image classification and semantic segmentation confirm the advantage of our approach. The proposed idea does not require any modifications in the model architecture and can be easily combined with existing strategies aiming to improve the performance of multi-exit neural networks.

In domain generalization (DG), the target domain is unknown when the model is being trained, and the trained model should successfully work on an arbitrary (and possibly unseen) target domain during inference. This is a difficult problem, and despite active studies in recent years, it remains a great challenge. In this paper, we take a simple yet effective approach to tackle this issue. We propose test-time style shifting, which shifts the style of the test sample (that has a large style gap with the source domains) to the nearest source domain that the model is already familiar with, before making the prediction. This strategy enables the model to handle any target domains with arbitrary style statistics, without additional model update at test-time. Additionally, we propose style balancing, which provides a great platform for maximizing the advantage of test-time style shifting by handling the DG-specific imbalance issues. The proposed ideas are easy to implement and successfully work in conjunction with various other DG schemes. Experimental results on different datasets show the effectiveness of our methods.

A fundamental challenge to providing edge-AI services is the need for a machine learning (ML) model that achieves personalization (i.e., to individual clients) and generalization (i.e., to unseen data) properties concurrently. Existing techniques in federated learning (FL) have encountered a steep tradeoff between these objectives and impose large computational requirements on edge devices during training and inference. In this paper, we propose SplitGP, a new split learning solution that can simultaneously capture generalization and personalization capabilities for efficient inference across resource-constrained clients (e.g., mobile/IoT devices). Our key idea is to split the full ML model into client-side and server-side components, and impose different roles to them: the client-side model is trained to have strong personalization capability optimized to each client’s main task, while the server-side model is trained to have strong generalization capability for handling all clients’ out-of-distribution tasks. We analytically characterize the convergence behavior of SplitGP, revealing that all client models approach stationary points asymptotically. Further, we analyze the inference time in SplitGP and provide bounds for determining model split ratios. Experimental results show that SplitGP outperforms existing baselines by wide margins in inference time and test accuracy for varying amounts of out-of-distribution samples.

While multi-exit neural networks are regarded as a promising solution for making efficient inference via early exits, combating adversarial attacks remains a challenging problem. In multi-exit networks, due to the high dependency among different submodels, an adversarial example targeting a specific exit not only degrades the performance of the target exit but also reduces the performance of all other exits concurrently. This makes multi-exit networks highly vulnerable to simple adversarial attacks. In this paper, we propose NEO-KD, a knowledge-distillation-based adversarial training strategy that tackles this fundamental challenge based on two key contributions. NEO-KD first resorts to neighbor knowledge distillation to guide the output of the adversarial examples to tend to the ensemble outputs of neighbor exits of clean data. NEO-KD also employs exit-wise orthogonal knowledge distillation for reducing adversarial transferability across different submodels. The result is a significantly improved robustness against adversarial attacks. Experimental results on various datasets/models show that our method achieves the best adversarial accuracy with reduced computation budgets, compared to the baselines relying on existing adversarial training or knowledge distillation techniques for multi-exit networks.

Traditional federated learning (FL) algorithms operate under the assumption that the data distributions at training (source domains) and testing (target domain) are the same. The fact that domain shifts often occur in practice necessitates equipping FL methods with a domain generalization (DG) capability. However, existing DG algorithms face fundamental challenges in FL setups due to the lack of samples/domains in each client’s local dataset. In this paper, we propose StableFDG, a style and attention based learning strategy for accomplishing federated domain generalization, introducing two key contributions. The first is style-based learning, which enables each client to explore novel styles beyond the original source domains in its local dataset, improving domain diversity based on the proposed style sharing, shifting, and exploration strategies. Our second contribution is an attention-based feature highlighter, which captures the similarities between the features of data samples in the same class, and emphasizes the important/common characteristics to better learn the domain-invariant characteristics of each class in data-poor FL scenarios. Experimental results show that StableFDG outperforms existing baselines on various DG benchmark datasets, demonstrating its efficacy.

Federated Learning (FL) is a decentralized machine learning paradigm that enables collaborative model training across dispersed nodes without having to force individual nodes to share data. However, its broad adoption is hindered by the high communication costs of transmitting a large number of model parameters. This paper presents EvoFed, a novel approach that integrates Evolutionary Strategies (ES) with FL to address these challenges. EvoFed employs a concept of `fitness-based information sharing’, deviating significantly from the conventional model-based FL. Rather than exchanging the actual updated model parameters, each node transmits a distance-based similarity measure between the locally updated model and each member of the noise-perturbed model population. Each node, as well as the server, generates an identical population set of perturbed models in a completely synchronized fashion using the same random seeds. With properly chosen noise variance and population size, perturbed models can be combined to closely reflect the actual model updated using the local dataset, allowing the transmitted similarity measures (or fitness values) to carry nearly the complete information about the model parameters. As the population size is typically much smaller than the number of model parameters, the savings in communication load is large. The server aggregates these fitness values and is able to update the global model. This global fitness vector is then disseminated back to the nodes, each of which applies the same update to be synchronized to the global model. Our analysis shows that EvoFed converges, and our experimental results validate that at the cost of increased local processing loads, EvoFed achieves performance comparable to FedAvg while reducing overall communication requirements drastically in various practical settings.

Mixup is a data augmentation method that generates new data points by mixing a pair of input data. While mixup generally improves the prediction performance, it sometimes degrades the performance. In this paper, we first identify the main causes of this phenomenon by theoretically and empirically analyzing the mixup algorithm. To resolve this, we propose GenLabel, a simple yet effective relabeling algorithm designed for mixup. In particular, GenLabel helps the mixup algorithm correctly label mixup samples by learning the class-conditional data distribution using generative models. Via theoretical and empirical analysis, we show that mixup, when used together with GenLabel, can effectively resolve the aforementioned phenomenon, improving the accuracy of mixup-trained model.

Recent proliferation of mobile devices and edge servers (e.g., small base stations) strongly motivates distributed learning at the wireless edge. In this paper, we propose a fast and secure distributed learning framework that utilizes computing resources at edge servers as well as distributed computing devices in tiered wireless edge networks. A fundamental lower bound is derived on the computational load that perfectly tolerates Byzantine attacks at both tiers. TiBroco, a hierarchical coding framework achieving this theoretically minimum computational load is proposed, which guarantees secure distributed learning by combating Byzantines. A fast distributed learning is possible by precisely allocating loads to the computing devices and edge servers, and also utilizing the broadcast nature of wireless devices. Extensive experimental results on Amazon EC2 indicate that our TiBroco allows significantly faster distributed learning than existing methods while guaranteeing full tolerance against Byzantine attacks at both tiers.

While federated learning (FL) allows efficient model training with local data at edge devices, among major issues still to be resolved are: slow devices known as stragglers and malicious attacks launched by adversaries. While the presence of both of these issues raises serious concerns in practical FL systems, no known schemes or combinations of schemes effectively address them at the same time. We propose Sageflow, staleness-aware grouping with entropy-based filtering and loss-weighted averaging, to handle both stragglers and adversaries simultaneously. Model grouping and weighting according to staleness (arrival delay) provides robustness against stragglers, while entropy-based filtering and loss-weighted averaging, working in a highly complementary fashion at each grouping stage, counter a wide range of adversary attacks. A theoretical bound is established to provide key insights into the convergence behavior of Sageflow. Extensive experimental results show that Sageflow outperforms various existing methods aiming to handle stragglers/adversaries.

In federated learning (FL), a number of distributed clients targeting the same task collaborate to train a single global model without sharing their data. The learning process typically starts from a randomly initialized or some pretrained model. In this paper, we aim at designing an initial model based on which an arbitrary group of clients can obtain a global model for its own purpose, within only a few rounds of FL. The key challenge here is that the downstream tasks for which the pretrained model will be used are generally unknown when the initial model is prepared. Our idea is to take a meta-learning approach to construct the initial model so that any group with a possibly unseen task can obtain a high-accuracy global model within only R rounds of FL. Our meta-learning itself could be done via federated learning among willing participants and is based on an episodic arrangement to mimic the R rounds of FL followed by inference in each episode. Extensive experimental results show that our method generalizes well for arbitrary groups of clients and provides large performance improvements given the same overall communication/computation resources, compared to other baselines relying on known pretraining methods.

We consider federated learning (FL) with multiple wireless edge servers having their own local coverage. We focus on speeding up training in this increasingly practical setup. Our key idea is to utilize the clients located in the overlapping coverage areas among adjacent edge servers (ESs); in the model-downloading stage, the clients in the overlapping areas receive multiple models from different ESs, take the average of the received models, and then update the averaged model with their local data. These clients send their updated model to multiple ESs by broadcasting, which acts as bridges for sharing the trained models between servers. Even when some ESs are given biased datasets within their coverage regions, their training processes can be assisted by adjacent servers through the clients in their overlapping regions. As a result, the proposed scheme does not require costly communications with the central cloud server (located at the higher tier of edge servers) for model synchronization, significantly reducing the overall training time compared to the conventional cloud-based FL systems. Extensive experimental results show remarkable performance gains of our scheme compared to existing methods. Our design targets latency-sensitive applications where edge-based FL is essential, e.g., when a number of connected cars/drones must cooperate (via FL) to quickly adapt to dynamically changing environments.

We characterize inter-cell interference in commercial three-dimensional NAND flash memory. By writing random data into 3D NAND and collecting sample means and sample variances of cell values corresponding to a particular set of input values in fixed relative neighboring cell locations, it is shown that the interference coming from any target cell locations can be measured. We observe that four neighboring cells, two along the same pipe and two along the same bit line, are responsible for most of the interference exerted on a given victim cell. Contrary to the general belief, the total amount of interference is found to be fairly significant even in 3D NAND; if compensated properly, the number of errors can be reduced significantly.

Wireless caching networks have been extensively researched as a promising technique for supporting the massive data traffic of multimedia services. Many of the existing studies on real-data traffic have shown that users of a multimedia service consecutively request multiple contents and this sequence is strongly dependent on the related list of the first content and/or the top referrer in the category. This paper thus introduces the notion of “temporary preference”, characterizing the behavior of users who are highly likely to request the next content from a certain target category (i.e., related content list). Based on this observation, this paper proposes both probabilistic caching and dynamic delivery policies for categorized contents and consecutive user demands. The proposed caching scheme maximizes the minimum of the cache hit rates for all users. In the delivery phase, a dynamic helper association policy for receiving multiple contents in a row is designed to reduce the delivery latency. By comparing with the content placement optimized for one-shot requests, numerical results verify the effects of categorized contents and consecutive user demands on the proposed caching and delivery policies.

Distributed learning plays a key role in reducing the training time of modern deep neural networks with massive datasets. In this article, we consider a distributed learning problem where gradient computation is carried out over a number of computing devices at the wireless edge. We propose hierarchical broadcast coding, a provable coding-theoretic framework to speed up distributed learning at the wireless edge. Our contributions are threefold. First, motivated by the hierarchical nature of real-world edge computing systems, we propose a layered code which mitigates the effects of not only packet losses at the wireless computing nodes but also straggling access points (APs) or small base stations. Second, by strategically allocating data partitions to nodes in the overlapping areas between cells, our technique achieves the fundamental lower bound on computational load to combat stragglers. Finally, we take advantage of the broadcast nature of wireless networks by which wireless devices in the overlapping cell coverage broadcast to more than one AP. This further reduces the overall training time in the presence of straggling APs. Experimental results on Amazon EC2 confirm the advantage of the proposed methods in speeding up learning. Our design targets any gradient descent based learning algorithms, including linear/logistic regressions and deep learning.

In wireless distributed computing systems, mobile devices that are connected wirelessly to the Fog (e.g., small base stations) collaboratively solve a given computational task. Unfortunately, wireless distributed computing systems suffer from packet losses due to severe channel fading. Moreover, a wireless device can drop out of the system when leaving the coverage of a master node in the Fog layer. We model this unreliability between a device and a master node as a packet erasure channel. When a packet fails to be detected at the receiver, the corresponding packet is retransmitted, which would significantly increase the overall run-time to finish the task. We take a coding-theoretic approach to tackle this straggler-like problem in wireless distributed computing. We first investigate the expected latency using an$(n, k)$maximum-distance separable (MDS) code. We obtain the lower and upper bounds on the latency in closed forms and provide guidelines to design MDS codes depending on thechannelcondition characterized by packet erasure probability. Then, we introduce another important performance metric calledminimum latency, and also provide guidelines on designing optimal codes. Based on optimal codes, we obtain the performance curves of achievable minimum latency and achievable workload as functions of packet erasure probability.

Learning novel concepts while preserving prior knowledge is a long-standing challenge in machine learning. The challenge gets greater when a novel task is given with only a few labeled examples, a problem known as incremental few-shot learning. We propose XtarNet, which learns to extract task-adaptive representation (TAR) for facilitating incremental few-shot learning. The method utilizes a backbone network pretrained on a set of base categories while also employing additional modules that are meta-trained across episodes. Given a new task, the novel feature extracted from the meta-trained modules is mixed with the base feature obtained from the pretrained model. The process of combining two different features provides TAR and is also controlled by meta-trained modules. The TAR contains effective information for classifying both novel and base categories. The base and novel classifiers quickly adapt to a given task by utilizing the TAR. Experiments on standard image datasets indicate that XtarNet achieves state-of-the-art incremental few-shot learning performance. The concept of TAR can also be used in conjunction with existing incremental few-shot learning methods; extensive simulation results in fact show that applying TAR enhances the known methods significantly.

Current distributed learning systems suffer from serious performance degradation under Byzantine attacks. This paper proposes Election Coding, a coding-theoretic framework to guarantee Byzantine-robustness for distributed learning algorithms based on signed stochastic gradient descent (SignSGD) that minimizes the worker-master communication load. The suggested framework explores new information-theoretic limits of finding the majority opinion when some workers could be attacked by adversary, and paves the road to implement robust and communication-efficient distributed learning algorithms. Under this framework, we construct two types of codes, random Bernoulli codes and deterministic algebraic codes, that tolerate Byzantine attacks with a controlled amount of computational redundancy and guarantee convergence in general non-convex scenarios. For the Bernoulli codes, we provide an upper bound on the error probability in estimating the signs of the true gradients, which gives useful insights into code design for Byzantine tolerance. The proposed deterministic codes are proven to perfectly tolerate arbitrary Byzantine attacks. Experiments on real datasets confirm that the suggested codes provide substantial improvement in Byzantine tolerance of distributed learning systems employing SignSGD.

In wireless caching networks, a user generally has a concrete purpose of consuming contents in a certain preferred category, and requests multiple contents in sequence. While most existing research on wireless caching and delivery has focused only on one-shot requests, the popularity distribution of contents requested consecutively is definitely different from the one-shot request and has been not considered. Also, especially from the perspective of the service provider, it is advantageous for users to consume as many contents as possible. Thus, this paper proposes two cache allocation policies for categorized contents and consecutive user demands, which maximize 1) the cache hit rate and 2) the number of consecutive content consumption, respectively. Numerical results show how categorized contents and consecutive content requests have impacts on the cache allocation.

We study the potential enhancement of the read access speed in high-performance solid-state drives (SSDs) by coding, given speed variations across the multiple flash interfaces and assuming occasional local memory failures. Our analysis is based on a queuing model that incorporates both read request failures and NAND element failures. The NAND element failure in the present context reflects various limitations on the memory element level such as bad blocks, dies or chips that cannot be corrected by error control coding (ECC) typically employed to protect pages read off the NAND cells. Our analysis provides a clear picture of the storage-overhead and read-latency trade-offs given read failures and NAND element failures. We investigate two different ways to mitigate the effect of NAND element failures using the notion of multi-class jobs with different priorities. A strong motivation for this work is to understand the reliability requirement of NAND chip components given an additional layer of failure protection, under the latency/storage-overhead constraints.

In wireless caching networks, each user generally consumes more than one content in a row, and the number of consecutive demands could vary for different users. In addition, popular contents are usually classified into several categories. In this case for consecutive user demands, the content popularity model largely depends on the previously consumed contents, i.e., contents that belong to the same category as the previously consumed content would be highly popular. Based on this observation, this paper proposes an optimal probabilistic caching policy for consecutive user demands in categorized contents. The proposed caching scheme maximizes the minimum of the success probabilities for content delivery of all users when individual users request different numbers of contents in a row. Comparing with the content placement optimized for one-shot request, intensive numerical results verify the impacts of categorized contents and consecutive user demands on the caching policy.

Handling previously unseen tasks after given only a few training examples continues to be a tough challenge in machine learning. We propose TapNets, neural networks augmented with task-adaptive projection for improved few-shot learning. Here, employing a meta-learning strategy with episode-based training, a network and a set of per-class reference vectors are learned across widely varying tasks. At the same time, for every episode, features in the embedding space are linearly projected into a new space as a form of quick task-specific conditioning. The training loss is obtained based on a distance metric between the query and the reference vectors in the projection space. Excellent generalization results in this way. When tested on the Omniglot, miniImageNet and tieredImageNet datasets, we obtain state of the art classification accuracies under various few-shot scenarios.

We suggest a general framework for network-coded Practical Byzantine Fault Tolerant (PBFT) consensus for enabling agreement among distributed nodes under Byzantine attacks. The suggested protocol generalizes existing replication and sharding schemes which are frequently used for consensus in current blockchain systems. Using the proposed algorithm, it is possible to reach a consensus when the available bandwidth is considerably smaller on individual links compared to that required for conventional schemes. It is shown that there exists an upper bound on the number of nodes that can participate in the protocol, given a maximum bandwidth constraint across all pairwise links. Furthermore, the protocol that achieves the upper bound is provided by using a set of constant weight codes.

Coded computation is a framework which provides redundancy in distributed computing systems to speed up large-scale tasks. Although most existing works assume error-free scenarios, the link failures are common in current wired/wireless networks. In this paper, we consider the straggler problem in distributed computing systems with link failures, by modeling the links between the master node and worker nodes as packet erasure channels. We first analyze the latency in this setting using an (n, k) maximum distance separable (MDS) code. Then, we consider a setup where the number of retransmissions is limited due to the bandwidth constraint. By formulating practical optimization problems related to latency, bandwidth and probability of successful computation, we obtain achievable performance curves as a function of packet erasure probability.

Coded distributed computing has been considered as a promising technique which makes large-scale systems robust to the "straggler" workers. Yet, practical system models for distributed computing have not been available that reflect the clustered or grouped structure of real-world computing servers. Also, the large variations in the computing power and bandwidth capabilities across different servers have not been properly modeled. We suggest a group-based model to reflect practical conditions and develop an appropriate coding scheme for this model. The suggested code, called group code, employs parallel encoding for each group. We show that the suggested coding scheme can asymptotically achieve optimal computing time in the regime of infinite n, the number of workers. While theoretical analysis is conducted in the asymptotic regime, numerical results also show that the suggested scheme achieves near-optimal computing time for any finite but reasonably large n. Moreover, we demonstrate that decoding complexity of the suggested scheme is significantly reduced by the virtue of parallel decoding.

In this paper, we consider the straggler problem of the high-dimensional matrix multiplication over distributed workers. To tackle this problem, we propose an irregular-product-coded computation, which is a generalized scheme of the standard-product-coded computation proposed in [1]. Introducing the irregularity to the product-coded matrix multiplication, one can further speed up the matrix multiplication, enjoying the low decoding complexity of the product code. The idea behind the irregular product code introduced in [2] is allowing different code rates for the row and column constituent codes of the product code. We provide a latency analysis of the proposed irregular-product-coded computation. In terms of the total execution time, which is defined by a function of the computation time and decoding time, it is shown that the irregular-product-coded scheme outperforms other competing schemes including the replication, MDS-coded and standard-product-coded schemes in a specific regime.

This paper investigates interplay among storage overhead, bandwidth requirement, and security constraint in distributed storage. In the model used in our analysis, storage nodes are dispersed in multiple clusters. When a node fails, necessary content gets restored by downloading data from different nodes that may possibly be in other clusters. The bandwidth required for transferring data for node repair is assumed more scarce for cluster-to-cluster links than the links connecting intra-cluster nodes. Eavesdropping takes place on links across clusters only, and a fraction of the total number of clusters is assumed compromised. When a cluster is compromised, any repair traffic going in and out of it is eavesdropped. For this clustered model with eavesdroppers, we analyze the security of distributed storage systems (DSSs) and provide guidelines on designing system solutions for securing the data. First, under the setting of functional repair, we derive a general upper bound on the secrecy capacity, the maximum data size that can be stored in DSSs with perfect secrecy. In the practically important bandwidth-limited regime where the node storage size is equal to the repair bandwidth, the upper bound is shown to be achievable through proposed code constructions. Moreover, we obtain a closed-form expression for the required system resources-node storage size and repair bandwidth-to store a given amount of data with perfect secrecy. Second, we investigate the behavior of secrecy capacity as the number of compromised clusters increases. According to our mathematical analysis, the secrecy capacity decreases as a quadratic function until the number of compromised clusters reaches a certain threshold. Finally, based on the fundamental relationship between the system resources and the secrecy capacity, we provide a guideline on balancing intra- and cross-cluster repair bandwidths depending on the given system security level.

In this paper, we propose a joint dynamic power control and user pairing algorithm for power-efficient and delay-constrained hybrid multiple access systems. In a hybrid multiple access system, user pairing determines whether the transmitter serves as a certain user by orthogonal multiple access (OMA) or non-orthogonal multiple access (NOMA). The proposed optimization framework minimizes the long-term time-average transmit power expenditure while reducing the queuing delay and guaranteeing the minimum time-average data rates. The proposed technique observes both channel and queue state information and adjusts queue backlogs to avoid an excessive queueing delay by appropriate user pairing and power allocation. Furthermore, the flexible use of resources is captured in the proposed algorithm by employing NOMA. The data-intensive simulation results show that the proposed scheme for power allocation and user scheduling achieves a balance among multiple performance goals, i.e., power efficiency, queueing delay, and data rate.

Coding for distributed computing supports low-latency computation by relieving the burden of straggling workers. While most existing works assume a simple master-worker model, we consider a hierarchical computational structure consisting of groups of workers, motivated by the need to reflect the architectures of real-world distributed computing systems. In this work, we propose a hierarchical coding scheme for this model, as well as analyze its decoding cost and expected computation time. Specifically, we first provide upper and lower bounds on the expected computing time of the proposed scheme. We also show that our scheme enables efficient parallel decoding, thus reducing decoding costs by orders of magnitude over non-hierarchical schemes. When considering both decoding cost and computing time, the proposed hierarchical coding is shown to outperform existing schemes in many practical scenarios.

Clustered distributed storage models real data centers where intra- and cross-cluster repair bandwidths are different. In this paper, exact-repair minimum-storage-regenerating (MSR) codes achieving capacity of clustered distributed storage are designed. Focus is given on two cases:$\epsilon=0$and$\epsilon=1/(n-k)$, where$\epsilon$is the ratio of the available cross- and intra-cluster repair bandwidths,$n$is the total number of distributed nodes and$k$is the number of contact nodes in data retrieval. The former represents the scenario where cross-cluster communication is not allowed, while the latter corresponds to the case of minimum cross-cluster bandwidth allowing minimum storage overhead. For the$\epsilon=0$case, two types of locally repairable codes are proven to achieve the MSR point. As for$\epsilon=1/(n-k)$, MDS codes achieve the MSR points for$n=Lk$, where$L$is the number of clusters.

This paper considers one-hop device-to-device-assisted wireless caching networks that cache video files of varying quality levels, with the assumption that the base station can control the video quality but cache-enabled devices cannot. Two problems arise in such a caching network: file placement problem and node association problem. This paper suggests a method to cache videos of different qualities, and thus of varying file sizes, by maximizing the sum of video quality measures that users can enjoy. There exists an interesting tradeoff between video quality and video diversity, i.e., the ability to provision diverse video files. By caching high-quality files, the cache-enabled devices can provide high-quality video, but cannot cache a variety of files. Conversely, when the device caches various files, it cannot provide a good quality for file-requesting users. In addition, when multiple devices cache the same file but their qualities are different, advanced node association is required for file delivery. This paper proposes a node association algorithm that maximizes time-averaged video quality for multiple users under a playback delay constraint. In this algorithm, we also consider request collision, the situation where several users request files from the same device at the same time, and we propose two ways to cope with the collision: scheduling of one user and non-orthogonal multiple access. Simulation results verify that the proposed caching method and the node association algorithm work reliably.

Distributed storage systems suffer from significant repair traffic generated due to the frequent storage node failures. This paper shows that properly designed low-density parity-check (LDPC) codes can substantially reduce the amount of required block downloads for repair thanks to the sparse nature of their factor graph representation. In particular, with a careful construction of the factor graph, both low repair-bandwidth and high reliability can be achieved for a given code rate. First, a formula for the average repair bandwidth of LDPC codes is developed. This formula is then used to establish that the minimum repair bandwidth can be achieved by forcing a regular check node degree in the factor graph. Moreover, it is shown that given a fixed code rate, the variable node degree should also be regular to yield minimum repair bandwidth, under some reasonable minimum variable node degree constraint. It is also shown that for a given repair-bandwidth requirement, LDPC codes can yield substantially higher reliability than the currently utilized Reed-Solomon codes. Our reliability analysis is based on a formulation of the general equation for the mean-time-to-data-loss (MTTDL) associated with LDPC codes. The formulation reveals that the stopping number is closely related to the MTTDL. It is further shown that LDPC codes can be designed such that a small loss of repair-bandwidth optimality may be traded for a large improvement in erasure-correction capability and thus the MTTDL.

In this paper, we propose bi-directional cooperative non-orthogonal multiple access (NOMA). Compared to conventional NOMA, the main contributions of bi-directional cooperative NOMA can be explained in two directions: 1) the proposed NOMA system is still efficient when the channel gains of scheduled users are almost the same and 2) the proposed NOMA system operates well without accurate channel-state information at the base station. In a two-user scenario, the closed-form ergodic capacity of bi-directional cooperative NOMA is derived, and it is proven to be better than those of other techniques. Based on the ergodic capacity, the algorithms to find optimal power allocations maximizing the user fairness and sum rate are presented. Outage probability is also derived, and we show that bi-directional cooperative NOMA achieves a power gain over uni-directional cooperative NOMA and a diversity gain over non-cooperative NOMA and orthogonal multiple access (OMA). We finally extend the bi-directional cooperative NOMA to a multiuser model. The analysis of ergodic capacity and outage probability in a two-user scenario is numerically verified. Also, simulation results show that bi-directional cooperative NOMA provides better data rates than the existing NOMA schemes as well as OMA in a multiuser scenario.

This paper considers the security issue of practical distributed storage systems (DSSs) which consist of multiple clusters of storage nodes. Noticing that actual storage nodes constituting a DSS are distributed in multiple clusters, two novel eavesdropper models - the node-restricted model and the cluster-restricted model - are suggested which reflect the clustered nature of DSSs. In the node-restricted model, an eavesdropper cannot access the individual nodes, but can eavesdrop incoming/outgoing data for Lccompromised clusters. In the cluster-restricted model, an eavesdropper can access a total of l individual nodes but the number of accessible clusters is limited to Lc. We provide an upper bound on the securely storable data for each model, while a specific network coding scheme which achieves the upper bound is obtained for the node-restricted model, given some mild condition on the node storage size.

We study potential enhancement of the read access speed in high-performance solid-state drives (SSDs) by coding, given speed variations across the multiple flash interfaces and assuming occasional local memory failures. Our analysis is based on a queuing model that incorporates both read request failures and node failures. It provides a clear picture on the coding-overhead and read-access-time trade-offs given read failures and node failures. The node failure in the present context reflects various limitations on the memory element level such as page failures, block failures or channel failures that occur during the access of stored data from NAND flash memory chips. A strong motivation for this work is to understand the reliability requirement of NAND chip components given a layer of erasure protection across nodes, under the latency/storage-overhead constraints.

A new system model reflecting the clustered structure of distributed storage is suggested to investigate interplay between storage overhead and repair bandwidth as storage node failures occur. Large data centers with multiple racks/disks or local networks of storage devices (e.g., sensor network) are good applications of the suggested clustered model. In realistic scenarios involving clustered storage structures, repairing storage nodes using intact nodes residing in other clusters are more bandwidth consuming than restoring nodes based on information from intra-cluster nodes. Therefore, it is important to differentiate between intra-cluster repair bandwidth and cross-cluster repair bandwidth in modeling distributed storage. Capacity of the suggested model is obtained as a function of fundamental resources of distributed storage systems, namely, node storage capacity, intra-cluster repair bandwidth, and cross-cluster repair bandwidth. The capacity is shown to be asymptotically equivalent to a monotonic decreasing function of number of clusters, as the number of storage nodes increases without bound. Based on the capacity expression, feasible sets of required resources which enable reliable storage are obtained in a closed-form solution. Specifically, it is shown that the cross-cluster traffic can be minimized to zero (i.e., intra-cluster local repair becomes possible) by allowing extra resources on storage capacity and intra-cluster repair bandwidth, according to the law specified in the closed form. The network coding schemes with zero cross-cluster traffic are defined as intra-cluster repairable codes, which are shown to be a class of the previously developed locally repairable codes.

This paper investigates spectral shaping of multi-carrier-modulation waveforms based on combination of Nyquist windowing and subband filtering. The combined windowing/filtering allows simultaneous control on both subcarrier and subband spectra. When compared with the existing Nyquist windowing or subband filtering techniques under a fixed excess frame length constraint, the proposed scheme offers reduced sensitivity to carrier frequency and symbol timing offsets. Establishing an analytical tool based on the error spectrum stack consisting of the error signals evaluated at different signal delay positions, we explore the window-filter trade-off and provide the minimum interference power solution for given ranges of carrier frequency and symbol timing offsets. Our design targets low-latency applications having no provisions for high-precision synchronization and having potential need for spectrum aggregation.

Pilot reuse in multi-cell massive multi-input multi-output (MIMO) system is investigated where user groups with different priorities exist. Recent investigation on pilot reuse has revealed that when the ratio of the coherent time interval to the number of users is reasonably high, it is beneficial not to fully reuse pilots from interfering cells. This work finds the optimum pilot assignment strategy that would maximize the weighted sum rate (WSR) given the user groups with different priorities. A closed-form solution for the optimal pilot assignment is derived and is shown to make intuitive sense. Performance comparison shows that under wide range of channel conditions, the optimal pilot assignment that uses extra set of pilots achieves better WSR performance than conventional full pilot reuse.

Pilot contamination, caused by the reuse of pilots among interfering cells, remains a significant obstacle that limits the performance of massive multi-input multi-output antenna systems. To handle this problem, less aggressive reuse of pilots involving allocation of additional pilots for interfering users is closely examined in this paper. Hierarchical pilot reuse methods are proposed, which effectively mitigate pilot contamination and increase the net throughput of the system. Among the suggested hierarchical pilot reuse schemes, the optimal way of assigning pilots to different users is obtained in a closed-form solution, which maximizes the net sum-rate in a given coherence time. Simulation results confirm that when the ratio of the channel coherence time to the number of users in each cell is sufficiently large, less aggressive reuse of pilots yields significant performance advantage relative to the case, where all cells reuse the same pilot set.

Distributed storage systems suffer from significant repair traffic generated due to frequent storage node failures. This paper shows that properly designed low-density parity-check (LDPC) codes can substantially reduce the amount of required block downloads for repair thanks to the sparse nature of their factor graph representation. In particular, with a careful construction of the factor graph, both low repair-bandwidth and high reliability can be achieved for a given code rate. First, a formula for the average repair bandwidth of LDPC codes is developed. This formula is then used to establish that the minimum repair bandwidth can be achieved by forcing a regular check node degree in the factor graph. It is also shown that for a given repair-bandwidth overhead, LDPC codes can have substantially higher reliability than currently utilized Reed-Solomon (RS) codes. Our reliability analysis is based on a formulation of the general equation for the mean-time-to-data-loss (MTTDL) associated with LDPC codes. The formulation reveals that the stopping number is highly related to MTTDL. For code rates 1/2, 2/3, and 3/4, our results show that quasi-cyclic (QC) progressive-edge-growth (PEG) LDPC codes with variable node degree 2 allow 25% ~ 50% reduction in the repair bandwidth while maintaining higher MTTDL compared to currently employed RS codes.

Trapping sets strongly degrade performance of low-density parity check (LDPC) codes in the low-error-rate region. This creates significant difficulties for the deployment of LDPC codes to low-error-rate applications such as storage and wireless systems with no or limited retransmission options. We propose a novel technique for breaking trapping sets based on collaborative decoding that utilizes two different decoding modes. While the main decoding mode executes message passing based on the original parity check matrix of the corresponding LDPC code, the sub-decoding mode operates on a modified parity check matrix formed by removing a portion of check nodes in the factor graph representation of the given code. The modified parity check matrix is designed to promote a passing of correct information into erroneous variable nodes in the trapping set. Theoretical properties of the proposed trapping-set-breaking technique have been established based on the notion of the improved separation for the trapped variable nodes. Simulation results show that the proposed collaborative LDPC decoding scheme switching between the two decoding modes back and forth effectively breaks dominant trapping sets of various known types of regular and irregular LDPC codes.

In modern tape storage, user data are recorded and retrieved along multiple tracks of rapidly moving, flexible magnetic medium that give rise to a variety of channel impediments including occasional long erasures, more frequent amplitude fades as well as a large amount of random errors. This work considers reliable recovery of data from such tape channels using a novel concatenation of an inner Reed-Solomon (RS) code and an outer nonbinary low-density parity-check (LDPC) code. This particular concatenation scheme and a highly tailored iterative decoding algorithm are chosen to efficiently handle the assortment of the tape channel impediments while meeting the stringent target error rate constraint as well as key practical requirements of the mass tape storage system. Despite the use of a nonbinary LDPC code, the proposed scheme allows excellent performance-complexity tradeoffs. In stark contrast to any existing coding schemes that involve LDPC codes, the proposed concatenation strategy allows semianalytic error rate performance evaluation at rates below what is possible using modern computers, thus providing an ability to ensure satisfactory low-error-rate performance.

Two-dimensional (2D) cyclic codes are presented which correct any single occurrence of known 2D error patterns within a 2D array of bits. Applications for this type of codes include storage and display devices. The code construction begins with a generation of distinct syndrome sets for all targeted 2D error patterns. A method to refine the syndrome sets is then presented for making each syndrome set to contain distinct members, thereby guaranteeing full correction capability for the given list of known error patterns. Using an example construction, the effectiveness of the proposed coding approach is demonstrated versus the maximum-distance-separable (MDS) random-error-correcting code and known 2D burst-correcting codes for a 2D intersymbol interference (ISI) channel that yields a few dominant, but relatively large error patterns.

Two concatenated coding schemes based on fixed-rate Raptor codes are proposed for error control in NAND flash memory. One is geared for off-line recovery of uncorrectable pages and the other is designed for page error correction during the normal read mode. Both proposed coding strategies assume hard-decision decoding of the inner code with inner decoding failure generating erasure symbols for the outer Raptor code. Raptor codes allow low-complexity decoding of very long codewords while providing capacity-approaching performance for erasure channels. For the off-line page recovery scheme, one whole NAND block forms a Raptor codeword with each inner codeword typically made up of several Raptor symbols. An efficient look-up-table strategy is devised for Raptor encoding and decoding which avoids using large buffers in the controller despite the substantial size of the Raptor code employed. The potential performance benefit of the proposed scheme is evaluated in terms of the probability of block recovery conditioned on the presence of uncorrectable pages. In the suggested page-error-correction strategy, on the other hand, a hard-decision-iterating product code is used as the inner code. The specific product code employed in this work is based on row-column concatenation with multiple intersecting bits to allow the use of longer component codes. In this setting the collection of bits captured within each intersection of the row-column codes acts as the Raptor symbol(s), and the intersections of failed row codes and column codes are declared as erasures. The error rate analysis indicates that the proposed concatenation provides a considerable performance boost relative to the existing error correcting system based on long Bose-Chauduri-Hocquenghem (BCH) codes.

This paper focuses on two-dimensional (2D) soft-input soft-output (SISO) equalization to mitigate intersymbol interference (ISI) among symbols that arise within a 2D array of data cells. The proposed method is based on arranging multiple component equalizers to exchange soft information with one another to enhance decision quality in an iterative manner. The component equalizers are simple one-dimensional linear equalizers running in different directions and do not perform well enough individually in the challenging 2D ISI environment, but working together, they consistently reach high-quality decisions. Performance comparison is made with the reduced-state trellis-based equalizers as well as the conceptually straightforward 2D linear equalizers. The results indicate excellent complexity/performance trade-off options for the proposed scheme.

This paper is concerned with linear relay and destination filter design methods for the multi-user peer-to-peer amplify-and-forward relaying systems. Specifically, the relay and destination filter sets are developed which minimize the sum mean-squared-error (MSE). We first present a joint optimum relay and destination filter calculation method with an iterative algorithm. Motivated by the need to reduce computational complexity of the iterative scheme, we then formulate a simplified sum MSE minimization problem using the relay filter decomposability, which lead to two sub-optimum non-iterative design methods. One is based on zero-forcing channel-inversion and the other on minimum-mean-squared-error channel-inversion. Finally, we propose modified destination filter design methods which require only local channel state information between relay and a specific destination node. The simulation results verify that, compared with the optimum iterative method, the proposed non-iterative schemes suffer a marginal loss in performance while enjoying significantly improved implementation efficiencies.

A self-iterating soft equalizer (SISE) consisting of a few relatively weak constituent equalizers is shown to provide robust performance even in severe intersymbol interference (ISI) channels that exhibit deep nulls and valleys within the signal band. Constituent equalizers are allowed to exchange soft information in the absence of interleavers based on the method that are designed to handle significant correlation among their soft outputs. The resulting SISE works well as a stand-alone equalizer or as the equalizer component of a turbo equalization system. The performance advantages over existing methods are validated with bit-error-rate (BER) simulations and extrinsic information transfer (EXIT) chart analysis. It is shown that in turbo equalizer setting the SISE achieves performance closer to the maximum a posteriori probability equalizer than any other known schemes in very severe ISI channels.

Multilevel flash memories store more than one bit per storage cell and are further characterized by large word (page) sizes and very low target error rates. In this paper, a high-rate error control scheme is presented that uses inner trellis-coded modulation (TCM) for storing two bits per cell with five possible charge levels. The coded subset-label bits and the uncoded signal-label bits of TCM are independently protected by separate outer Reed-Solomon (RS) codes. The resulting scheme permits multistage decoding. Errors made by the TCM decoder in the subset-label bits occur in bursts and are corrected by the associated first RS decoder prior to determining signal-label bits and correcting errors in those bits by the associated second RS decoder. The multi-stage decoding avoids the significant spread of errors from subset-label bits into the generally larger number of signal-label bits which is typical for conventional serial RS-TCM concatenation when the inner TCM system operates at relatively low SNR. The error performance of the proposed scheme is evaluated at low error rates by a mixed simulation-analytic method. It is shown that the proposed scheme exhibits highly favorable performance vs. complexity tradeoffs compared to the other schemes.

This paper considers error-correcting codes designed to correct a finite set of known two-dimensional (2D) error patterns that can occur in a 2D array of bits. Obvious applications for this type of codes include storage and display devices. The specific codes designed in this paper are cyclic codes that can correct any single occurrences of dominant known error patterns that can occur anywhere in the 2D array. As example codes, rate-0.994 codes are constructed which target eight known 2D error patterns in a 63 × 63 bit array.

We consider flexible decoder implementation of low density parity check (LDPC) codes via compute-unified-device-architecture (CUDA) programming on graphics processing unit (GPU), a research subject of considerable recent interest. An important issue in LDPC decoder design based on CUDA-GPU is realizing coalesced memory access, a technique that reduces memory transaction time considerably. In previous works along this direction, it has not been possible to achieve coalesced memory access in both the read and write operations due to the asymmetric nature of the bipartite graph describing the LDPC code structure. In this paper, a new algorithm is proposed that enables coalesced memory access in both the read and write operations for one half of the decoding process - either the bit-to-check or the check-to-bit message passing. For the remaining half of the decoding step our scheme requires address transformation in both the read and write operations but one translating array is sufficient. We also describe the use of on-chip shared memory and texture cache. Overall, experimental results show that proposed GPU-based LDPC decoder achieves more than 234×-speedup compared to CPU-based LDPC decoders and also outperforms existing GPU-based decoders by a significant margin.

This letter is concerned with transmit and receive filter optimization for the K-user MIMO interference channel. Specifically, linear transmit and receive filter sets are designed which maximize the weighted sum rate while allowing each transmitter to utilize only the local channel state information. Our approach is based on extending the existing method of minimizing the weighted mean squared error (MSE) for the MIMO broadcast channel to the K-user interference channel at hand. For the case of the individual transmitter power constraint, however, a straightforward generalization of the existing method does not reveal a viable solution. It is in fact shown that there exists no closed-form solution for the transmit filter but simple one-dimensional parameter search yields the desired solution. Compared to the direct filter optimization using gradient-based search, our solution requires considerably less computational complexity and a smaller amount of feedback resources while achieving essentially the same level of weighted sum rate. A modified filter design is also presented which provides desired robustness in the presence of channel uncertainty.

This letter discusses a receiver-side channel estimation algorithm well-suited to turbo equalizers for multiple-input multiple-output (MIMO) systems. The proposed technique is a Kalman-based channel estimator that runs on parallel single-input single-output (SISO) channels. Soft-decision-feedback interference cancellation is utilized to reduce the MIMO channel estimation problem into multiple SISO channel estimation problems. Unlike existing methods, however, the inherent correlation that exists among the output samples of the successive interference canceller is suppressed via careful puncturing of observation samples. The quality of soft decisions and channel estimates are also continuously monitored and incorporated in the Kalman filter update process.

Provable lower bounds are presented for the information rate I(X; X+S+N) where X is the symbol drawn independently and uniformly from a finite-size alphabet, S is a discrete-valued random variable (RV) and N is a Gaussian RV. It is well known that with S representing the precursor intersymbol interference (ISI) at the decision feedback equalizer (DFE) output, I(X; X+S+N) serves as a tight lower bound for the symmetric information rate (SIR) as well as capacity of the ISI channel corrupted by Gaussian noise. When evaluated on a number of well-known finite-ISI channels, these new bounds provide a very similar level of tightness against the SIR to the conjectured lower bound by Shamai and Laroia at all signal-to-noise ratio (SNR) ranges, while being actually tighter when viewed closed up at high SNRs. The new lower bounds are obtained in two steps: First, a “mismatched” mutual information function is introduced which can be proved as a lower bound to I(X; X+S+N). Secondly, this function is further bounded from below by an expression that can be computed easily via a few single-dimensional integrations with a small computational load.

We design a self-iterating soft equalizer (SISE) consisting of several suboptimal equalizers that are weak individually but, when working together, show good performance. In order to process correlated soft information through serially concatenated modules, a sophisticated method to generate the extrinsic information is proposed that suppresses the correlation effect between the soft information of suboptimal equalizers. This algorithm performs well in turbo equalization system as well as the classic uncoded equalization system. The performance advantages are validated with bit-error-rate (BER) simulations and extrinsic information transfer (EXIT) chart analysis.

This paper discusses a technique for analyzing real data from flash memory cells. The goal is to identify and isolate various sources that cause the shifts and variations of the read values with respect to the intended write values. The analysis reveals how the neighboring cells interfere with the victim cell. Using the proposed analysis technique, the contribution of a specified set of neighboring cells towards the random read variation of the victim cell can be also quantified accurately.

This paper is concerned with transmit and receive filter optimization for the K-user MIMO interference channel. Specifically, linear transmit and receive filter sets are designed which maximize the weighted sum rate while allowing each transmitter to utilize only the local channel state information. Our approach is based on extending the existing method of minimizing the weighted mean squared error (MSE) for the MIMO broadcast channel to the K-user interference channel at hand. For the case of the individual transmitter power constraint, however, a straightforward generalization of the existing method does not reveal a viable solution. It is in fact shown that there exists no closed-form solution for the transmit filter but simple one-dimensional parameter search yields the desired solution. Compared to the direct filter optimization using gradient-based search, our solution requires considerably less computational complexity and a smaller amount of feedback resources while achieving essentially the same level of weighted sum rate.

We design a soft-in soft-out (SISO) decision feedback equalizer (DFE) that performs better than its linear counterpart in turbo equalizer (TE) setting. Unlike previously developed SISO-DFEs, the present DFE scheme relies on extrinsic information formulation that directly takes into account the error propagation effect. With this new approach, both error rate simulation and the extrinsic information transfer (EXIT) chart analysis indicate that the proposed SISO-DFE is superior to the well-known SISO linear equalizer (LE). This result is in contrast with the general understanding today that the error propagation effect of the DFE degrades the overall TE performance below that of the TE based on a LE. We also describe a new extrinsic information combining strategy involving the outputs of two DFEs running in opposite directions, that explores error correlation between the two sets of DFE outputs. When this method is combined with the new DFE extrinsic information formulation, the resulting "bidirectional" turbo-DFE achieves excellent performance-complexity tradeoffs compared to the TE based on the BCJR algorithm or on the LE. Unlike turbo LE or turbo DFE, the turbo BiDFE's performance does not degrade significantly as the feedforward and feedback filter taps are constrained to be time-invariant.

We consider channel estimation specific to turbo equalization for multiple-input multiple-output (MIMO) wireless communication. We develop a soft-decision-driven sequential algorithm geared to the pipelined turbo equalizer architecture operating on orthogonal frequency division multiplexing (OFDM) symbols. One interesting feature of the pipelined turbo equalizer is that multiple soft-decisions become available at various processing stages. A tricky issue is that these multiple decisions from different pipeline stages have varying levels of reliability. This paper establishes an effective strategy for the channel estimator to track the target channel, while dealing with observation sets with different qualities. The resulting algorithm is basically a linear sequential estimation algorithm and, as such, is Kalman-based in nature. The main difference here, however, is that the proposed algorithm employs puncturing on observation samples to effectively deal with the inherent correlation among the multiple demapper/decoder module outputs that cannot easily be removed by the traditional innovations approach. The proposed algorithm continuously monitors the quality of the feedback decisions and incorporates it in the channel estimation process. The proposed channel estimation scheme shows clear performance advantages relative to existing channel estimation techniques.

The error-pattern correcting code (EPCC) is a code designed to correct frequently observed error cluster patterns of the intersymbol interference (ISI) channel. This paper focuses on developing theoretical understanding of the performance of serial concatenation of the EPCC with an outer recursive systematic convolutional code (RSCC) in ISI channel environments. To analyze the performance of this EPCC-RSCC concatenation, an upper union bound on the maximum-likelihood (ML) bit-error rate (BER), averaged over all possible interleavers, is derived which offers crucial insights into the error floor behavior of the matching turbo decoder. The ML bound is also used to compare the performance of EPCC-RSCC to that of a stand-alone RSCC in serial concatenation to precoded and nonprecoded ISI channels. This comparison shows that by targeting the low Hamming-weight interleaved errors of the RSCC, which result in low Euclidean distance error events in the channel detector, EPCC-RSCC exhibits a much lower BER floor compared to conventional schemes, especially for high rate applications and short interleaver lengths. The error rate performance of an iterative suboptimal turbo equalizer (TE), called TE-EPCC, is also demonstrated to converge close to the ML bound at high SNR.

We utilize a pair of decision feedback equalizers (DFEs) operating in opposite directions in turbo equalization setting to remove the effect of intersymbol interference (ISI) at the receiver. With a specific residual interference processing strategy proposed, the bi-directional DFE (BiDFE) are free from any significant error propagation. A diversity combining scheme is also proposed that effectively combines the extrinsic outputs of two opposite direction DFEs to minimize any correlation that may exist between them. A resulting scheme is a low-complexity equalizer that closely approaches the performance of the much more complex BCJR algorithm at the expense of an increased number of decoder-equalizer iterations. The BiDFE turbo equalizer also provides considerably better performance than the well-known soft linear minimum mean square error (MMSE) equalizer in severe ISI channels. The performance advantages are validated with bit-error-rate (BER) simulations and extrinsic information transfer (EXIT) charts analysis.

We consider channel estimation specific to turbo equalization for multiple-input multiple-output (MIMO) wireless communication. We develop soft-decision-driven sequential algorithms geared to a specific pipelined turbo equalizer architecture operating on orthogonal frequency division multiplexing (OFDM) symbols. One interesting feature of the pipelined turbo equalizer is that multiple soft-decisions become available at various processing stages. A tricky issue is the fact that these multiple decisions from different pipeline stages have correlated decision errors as well as varying levels of reliability. This paper establishes an optimization strategy for the channel estimator to track the target channel while dealing with observation sets with different qualities. The resulting algorithm is basically a linear sequential estimation algorithm and, as such, is Kalman-like in nature. The main difference here, however, is that the proposed algorithm must deal with the inherent correlation that exist among the multiple module outputs that cannot easily be removed by the traditional innovation approach. The proposed algorithm continuously monitor the quality of the feedback decisions and incorporate it in the channel estimation process. The proposed channel estimation schemes show certain performance and complexity advantages over existing EM-based algorithms.

The error pattern correcting code (EPCC) can be constructed to provide a syndrome decoding table targeting the dominant error events of an inter-symbol interference channel at the output of the Viterbi detector. For the size of the syndrome table to be manageable and the list of possible error events to be reasonable in size, the codeword length of EPCC needs to be short enough. However, the rate of such a short length code will be too low for hard drive applications. To accommodate the required large redundancy, it is possible to record only a highly compressed function of the parity bits of EPCC's tensor product with a symbol correcting code. In this paper, we show that the proposed tensor error-pattern correcting code (T-EPCC) is linear time encodable and also devise a low-complexity soft iterative decoding algorithm for EPCC's tensor product with q-ary LDPC (T-EPCC-qLDPC). Simulation results show that T-EPCC-qLDPC achieves almost similar performance to single-level qLDPC with a 1/2 KB sector at 50% reduction in decoding complexity. Moreover, 1 KB T-EPCC-qLDPC surpasses the performance of 1/2 KB single-level qLDPC at the same decoder complexity.

In this correspondence, we investigate the error probability bounds of a bit-interleaved space–time trellis coding (BISTTC) scheme, which concatenates bit-interleaved coded modulation (BICM) with a space–time trellis code (STTC). We focus on general block-fading channels, wherein each data packet or frame spans a number of independent fading blocks. BICM applied to such channel environments can effectively exploit both time and frequency selectivity, while a STTC maximizes the spacial diversity order. The exact pairwise error probability (PEP) and weight enumeration function (WEF) of BISTTC are used to evaluate the error bound. Due to the concatenation of an outer error correction code (ECC) and a STTC, the overall WEF of BISTTC is obtained by combining the WEF of the outer code with that of the STTC through an uniform interleaver. The main challenge here is to compute the WEF of a STTC for block-fading channels with reasonable complexity. We rely on constructing a composite state transition matrix based on a number of single-step virtual trellises, each corresponding to an independent fading block within a frame. We discuss how this approach reduces storage and computational requirements in the bound analysis, compared to the existing method of obtaining the state transition matrix through accumulation of single-step transition matrices. The derived bound is applicable to both spatially uncorrelated and correlated channels as well as to both flat and frequency-selective block-fading channels. The bound is shown to provide a reasonably close estimate of the simulated performance based on the turbo equalizer-like iterative processing of soft information between the STTC decoder and the ECC decoder.

We present a preceded reduced-complexity soft detection (PRCSD) algorithm for multiple-input multiple-output (MIMO) systems. The linear operations at both transmit and receive sides based on complex Householder transform convert the MIMO channel to be multiple-diagonal, spatially partial-response-like, so that error propagation is alleviated when applying reduced-complexity soft detection at the receiver. The transform results in unitary precoding and feedforward matrices so that neither transmit power boost nor noise enhancement is present. Performance analysis based on pairwise error probability (PEP) shows that PRCSD achieves larger diversity advantage than existing preceding and multiple-beamforming (MB) schemes, which basically attempt to transmit signals through diagonal independent sub-channels and thus may suffer a diversity loss. PRCSD can achieve full diversity as maximum likelihood (ML) detection in some scenarios while reducing complexity significantly

A decision-directed timing recovery scheme is proposed that maintains and updates a separate phase estimate path for each survivor data path in the maximum-likelihood sequence detection of intersymbol interference channels. For each survivor path, the phase estimate is updated recursively using symbol- decisions implied in the path. Unlike in the existing per-survivor timing recovery approach, there exists a single global timing loop that operates on a single stream of phase sequence released from the phase-estimating maximum-likelihood detector that is associated with the merged survivor path or the best up-to-date survivor path. The timing error detector itself is derived as a recursive formulation of the least square solution that minimizes error between the observation sequence and the clean expected signal sequence. Jitter analysis, stability analysis and tracking time simulation validate the proposed approach.

We propose a high-rate error-pattern control code based on a generator polynomial targeting a specific set of known dominant error patterns. This code is based on first constructing a low-rate cyclic code that possesses a distinct syndrome set for each target error pattern. This base code is then extended by simply applying the same generator polynomial to a larger message block. It is shown that the captured syndrome along with a soft metric can be used to correct a single occurrence of any target error pattern within the codeword with a high probability of accuracy. The proposed scheme outperforms, by a significant margin, conventional post-Viterbi error correction based on high-rate error detection coding. The performance comparison is provided for a high-density perpendicular recording model.

We present a precoded reduced-complexity soft detection (PRCSD) algorithm for spatial multiplexing systems. The linear operations at both transmit and receive sides based on complex Householder transform convert the multi-input multi-output (MIMO) channel to be multiple-diagonal, spatially partial-response-like, so that error propagation is alleviated when applying RCSD at the receiver. The transform results in unitary precoding and feedforward matrices so that neither transmit power boost nor noise enhancement is present. Performance analysis based on pairwise error probability (PEP) shows that PRCSD achieves higher diversity advantage than existing precoding and multiple-beamforming schemes, which basically attempt to transmit signals through diagonal independent sub-channels and thus may suffer diversity loss. PRCSD can achieve full diversity as ML detection in some scenarios while reducing complexity significantly.

A joint iterative estimator is developed that estimates both the carrier frequency offset (CFO) and data sequence for orthogonal frequency-division multiplexing systems. For frequency-selective fading channels, the estimator also incorporates channel response estimation. The estimator operates in the frequency domain, after the Fourier transformation. Convergence analysis shows that the CFO estimator converges to the actual value in the almost sure sense if the initial CFO is less than approximately one half of the subcarrier spacing. The complexity of the proposed algorithm can be made manageable by using proper windowing prior to the Fourier transformation and decision feedback techniques. A simulation study is also conducted to show the bit error rate as well as the mean squared error performances of the proposed algorithms.

We present a low complexity soft detection scheme well-suited to multi-input multi-output (MIMO) systems based on spatial domain multiplexing leading to layered space-time or space-frequency architecture. The proposed algorithm is based on trellis representation of the MIMO signals and a subsequent formulation of constrained-delay maximum a posterior (MAP) detection in conjunction with soft decision feedback (SDF). Decision feedback is broken into causal and noncausal parts in an effort to maximize the observation window while maintaining a reasonable computational load. Error rate simulations are conducted in the context of turbo-like iterative demapping and decoding (IDD). The resulting performance and required complexity are compared with those of maximum likelihood (ML) detection, sphere detection (SD), as well as the vertical BLAST (V-BLAST) processing scheme. We observe excellent performance/complexity tradeoffs with the proposed soft detection scheme for a number of modulation/channel scenarios.

We discuss an error detection technique geared to a prescribed set of error events. The traditional method of error detection and correction attempts to detect/correct as many erroneous bits as possible within a codeword, irrespective of the pattern of the error events. The proposed approach, on the other hand, is less concerned about the total number of erroneous bits it can detect, but focuses on specific error events of known types. We take perpendicular recording systems as an application example. Distance analysis and simulation can easily identify the dominant error events for the given noise environment and operating density. We develop a class of simple error detection parity check codes that can detect these specific error events. The proposed coding method, when used in conjunction with post-Viterbi error correction processing, provides a substantial performance gain compared to the uncoded perpendicular recording system.

In the context of iterative decoding and equalization (a.k.a. turbo equalization) of high density magnetic recording (MR) channels, we propose a low complexity soft-in soft-out (SISO) algorithm which implements the constrained delay a-posteriori probability (CD-APP) estimation utilizing either hard or soft decision feedback (HDF/SDF). Through BER simulation, we show that for an MR channel with user density 3.2, our proposed iterative scheme based on SDF enjoys a 6+ dB coding gain over the uncoded system and is superior to HDF by 2.2 dB at BER of 10/sup -5/. It also performs comparably to the iterative system in which the BCJR algorithm matched to a generalized E2PR4 (GE2PR4) target is used for channel detection. Through captured burst error statistics, we show that SDF can significantly mitigate the detrimental effect of error propagation typically observed in systems based on RDF. The short burst error feature of SDF is most attractive in light of an outer error correcting code (ECC), such as the Reed-Solomon code.

We consider turbo equalization for intersymbol interference (ISI) channels, wherein soft symbol decisions generated by the channel detector are iteratively exchanged with the outer error-correction decoder based on the turbo principle. Our work is based on low-complexity suboptimal soft-output channel detection using a constrained-delay (CD) a posteriori probability (APP) algorithm. Central to the proposed idea is the incorporation of effective decision-feedback schemes, which significantly reduce complexity while providing immunity against error propagation that typically plagues decision-feedback schemes. We observe that the effect of decision feedback is quite different on turbo equalization versus traditional, hard-decision-generating and noniterative equalization. In particular, we demonstrate that when the feedback scheme applied is inadequate for the given equalizer parameters and ISI condition, the extrinsic information generated by the equalizer becomes distinctly non-Gaussian, and the quality of soft information, as monitored by the trajectory of mutual information, fails to improve in the iterative process. We identify parameters of feedback-based CD-APP schemes that offer favorable complexity/performance tradeoffs, compared with existing turbo-equalization techniques.

A new carrier phase and frequency recovery scheme is proposed for multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) systems. The algorithm uses an extended Kalman filter (EKF) to estimate the instantaneous phase and frequency offset. A linear minimum mean squared error (LMMSE) data-channel extractor is used to isolate the phase and frequency dependent term from the received signal. The proposed algorithm can provide both phase and carrier frequency recovery and has lower complexity than other approaches in the literature. In addition there is very little latency associated with the proposed approach. Simulation results show that the proposed algorithm can track quickly carrier phase and frequency offset and the performance loss compared to the synchronous case is very small.

We introduce an alternative structure for computing the a posteriori probabilities (APPs) for state and transition sequences of a Markov source observed through a noisy output sequence. Compared to the well-established forward-backward recursion algorithm of Bahl et al. (1974), the proposed structure allows a reduction in computational complexity at the expense of increased memory requirements. Alternatively, for a similar complexity level, the proposed structure needs smaller memory when the input alphabet size is small.

A hard disk readback signal generator designed to provide noise-corrupted signals to a channel simulator has been implemented on a Xilinx Virtex textrmTME FPGA device. The generator simulates pulses sensed by read heads in hard drives. All major distortion and noise processes, such as intersymbol interference, transition noise, electronics noise, head and media nonlinearity, intertrack interference, and write timing error, can be generated according to the statistics and parameters defined by the user. Reconfigurable implementation enables an update of the signal characteristics in runtime. The user also has the flexibility to choose from a set of bitstreams to simulate particular combinations of noise and distortion. Such customized restructuring helps reduce the area consumption and hence virtually increase the capacity of the FPGA device. The time to generate the readback signals has been reduced by four orders compared to its software counterpart.

Transmitter diversity and coding techniques can be used in high data-rate wireless communications with orthogonal frequency division multiplexing (OFDM) to improve the performance. In this paper, we propose the use of QAM modulations with the constellation size larger than the currently used modulations in HYPERLAN/2, in order to achieve higher spectrum efficiency and data rate. To compensate for the performance loss associated with an extended constellation, we apply the low-density parity check (LDPC) code and introduce transmitter/receiver diversity to the HYPERLAN/2 system. We observe that the LDPC code shows better fading-resistant and error-correcting capabilities than the convolutional code, and the performance loss is completely compensated with the use of diversity techniques.

We develop a new method for simple soft-output detection. Like other soft-output detectors, our approach also utilizes the trellis structure. However, in computing the state transition probabilities in the trellis, we model each bit as a linear regression of the channel outputs as well as the previous bits implied in the corresponding branch. The trellis depends not on the channel response but on the regression model parameter that is highly flexible. The resulting soft-output algorithm has a very simple structure, needing only a forward recursion. The amount of memory required is also small. Furthermore, this algorithm can easily handle colored/signal-dependent noise. We examine the performance of this algorithm for three ISI channels with different noise characteristics: additive white, colored, and colored and signal-dependent. To verify the quality of the soft decisions, an outer low-density parity check code is used. Results show that the proposed detector allows favorable complexity/performance tradeoffs in correlated/signal-dependent noise environment.

The application of low-density parity-check (LDPC) codes for use in high-density magnetic recording channels is considered. A first order position jitter model is assumed in order to include the effect of signal dependent transition noise present in high density longitudinal thin film recording. Coding gains using pattern dependent noise-predictive soft detection to account for the transition noise are also determined via simulation. Results show that LDPC code performance degrades in equalized (colored) additive noise, but exhibits remarkable performance in the presence of signal dependent transition noise, especially when used in conjunction with an appropriately optimized detector.

The effect of signal dependent jitter noise on channel capacity is investigated. Upper and lower bounds on capacity are computed numerically for channels with a mix of signal dependent jitter noise and additive white Gaussian noise. The resulting bounds allow for comparison of potential coding gain for differing amounts of jitter noise and varying code rates. The comparison provides insight into the effect jitter noise has on channel capacity and shows that in some cases there is significantly more coding gain possible when the noise is predominantly jitter noise.

Maximum and near-maximum likelihood sequence detectors in signal-dependent noise are discussed. It is shown that the linear prediction viewpoint allows a very simple derivation of the branch metric expression that has previously been shown as optimum for signal-dependent Markov noise. The resulting detector architecture is viewed as a noise predictive maximum likelihood detector that operates on an expanded trellis and relies on computation of branch-specific, pattern-dependent noise predictor taps and predictor error variances. Comparison is made on the performance of various low-complexity structures using the positional-jitter/width-variation model for transition noise. It is shown that when medium noise dominates, a reasonably low complexity detector that incorporates pattern-dependent noise prediction achieves a significant signal-to-noise ratio gain relative to the extended class 4 partial response maximum likelihood detector. Soft-output detectors as well as the use of soft decision feedback are discussed in the context of signal-dependent noise.

A delay-constrained sequence detector is considered for recording channels whose major impediments include intersymbol interference (ISI) and magnetic transition jitter noise. The jitter noise is data-dependent, and a given noise sample is correlated with neighboring noise samples. A sequence detector with a finite decision delay can be formulated in a finite dimensional vector space. For a correlated noise channel, the decision boundary is generally quadratic. We present a technique for obtaining a minimal set of hyperplanes approximating a quadratic decision boundary with a negligible performance loss. In this process, a distance measure, which is consistent with the notion of the effective SNR, is defined and used as a design parameter to trade the complexity and performance. As an achievable performance bound, we derive the effective SNR for the maximum-likelihood sequence detector (MLSD) for these channels. The performance of the partial response maximum likelihood (PRML) detector commonly adopted for current data storage channels as well as the Viterbi algorithm (VA) based on the traditional Euclidean metric, which serves as the MLSD for additive white Gaussian noise, are also analyzed and compared with that of the proposed signal space detector.

A signal space partitioning technique is presented for detecting symbols transmitted through intersymbol interference channels. The decision boundary is piecewise linear and is made up of several hyperplanes. The goal here is to minimize the number of hyperplanes for a given performance measure, namely, the minimum distance between any signal and the decision boundary, Unlike in Voronoi partitioning, individual hyperplanes are chosen to separate signal clusters rather than signal pairs. The convex regions associated with individual signals, which together form the overall decision region, generally overlap or coincide among in-class signals. The technique leads to an asymptotically optimum detector when the target distance is set at half the minimum distance associated with the maximum-likelihood sequence detector. Complexity and performance can be easily traded as the target distance is a flexible design parameter.

A signal-space detector estimates the channel input symbol based on the location of the finite-length observation signal in a multi-dimensional signal-space. The decision boundary is formed by a set of hyperplanes. The resulting detector structure consists of linear discriminant functions, threshold detectors, and a Boolean logic function. Our goal is to minimize the number of linear discriminant functions (hyperplanes) with the same or negligible performance loss relative to the maximum likelihood sequence detector. Given all possible fixed-length signal sequences, our procedure finds a minimal set of hyperplanes by which every pair of opposite class signals can be separated by distance no less than the prescribed minimum distance. The proposed methods are applied to practical magnetic recording channels.

Binary symbol detection based on a sequence of finite observation signals is formulated in the multidimensional signal space. A systematic space partitioning method is proposed to divide the entire space into two decision regions using a set of hyperplanes. The resulting detector structure consists of K parallel linear classifiers followed by a K-to-1 Boolean mapper, and is well suited to high-speed implementation. Compared to direct implementation of the fixed-delay tree search (FDTS) detection rule, the proposed signal-space formulation results in a considerable saving in digital hardware. Examples taken from binary-input intersymbol interference (ISI) channels are used to demonstrate the proposed technique. Block processing strategies suitable for high-speed applications are also discussed.

Unlike in many communication channels, the read signals in thin-film magnetic recording channels are corrupted by non-Gaussian, data-dependent noise and nonlinear distortions. In this work we use feedforward neural networks-a multilayer perceptron and its simplified variations-to equalize these signals. We demonstrate that they improve the performance of data recovery schemes in comparison with conventional equalizers. The variations of the MLP equalizer are suitable for the low complexity VLSI implementation required in data storage systems. We also present a novel training criterion designed to reduce the probability of error for the recovered digital data. The results were obtained both from experimental data and from a software recording channel simulator using thin-film disk and magnetoresistive head models.

We present methods to systematically design a feedforward neural-network detector from the knowledge of the channel characteristics. Its performance is compared with the conventional linear equalizer in a magnetic recording channel suffering from signal-dependent noise and nonlinear intersymbol interference. The superiority of the nonlinear schemes are clearly observed in all cases studied, especially in the presence of severe nonlinearity and noise. We also show that the decision boundaries formed by a theoretically derived neural-network classifier are geometrically close to those of a neural network trained by the backpropagation algorithm. The approach in this work is suitable for quantifying the gain in using a neural-network method as opposed to linear methods in the classification of noisy patterns.

This paper addresses the data detection problem of intersymbol interference (ISI) channels with a specific modulation code-constraint known as the (d, k) run-length-limited (RLL) constraint, a popular modulation code-constraint for data storage channels as well as certain communication channels. A computationally efficient sequence detection algorithm is proposed which yields a performance close to that of the maximum likelihood sequence detector when applied to such ISI channels. The proposed detector is derived as a high signal-to-noise ratio approximation to the delay-constrained optimum detector, one which minimizes the symbol error probability given a fixed decision-delay constraint. The proposed algorithm is essentially a fixed-delay tree search (FDTS) algorithm with systematic ambiguity checking and is closely related to existing finite-depth tree search algorithms. It is observed that long critical error events common in uncoded ISI channels are eliminated by the RLL constraint. Based on this observation, we show that for some important RLL constrained channels, the proposed FDTS algorithm yields the same minimum Euclidean distance between distinguishable channel output sequences as the unconstrained maximum likelihood sequence detector.>