Granite-speech LLMs are compact and efficient speech language models specifically designed for English ASR1and automatic speech translation (AST). The models were trained by modality aligning granite-3.3-instruct to speech on publicly available open-source corpora. Comprehensive benchmarking on English ASR shows that they outperform several competitors’ models that were trained on orders of magnitude more proprietary data, and they keep pace on English-to-X AST for major European languages, Japanese, and Mandarin. The speech-specific components are: a conformer acoustic encoder using block attention and self-conditioning trained with connectionist temporal classification, a windowed query-transformer speech modality adapter used to do temporal downsampling of the acoustic embeddings and map them to the LLM text embedding space, and LoRA adapters to further fine-tune the text LLM. The models are freely available on HuggingFace2under a permissive Apache 2.0 license.1The latest models (revision 3.3.2) support multilingual ASR in English, French, German, Spanish and Portuguese and bidirectional speech translation to and from English. This paper covers the initial English-only release.2https://huggingface.co/ibm-granite/granite-speech-3.3-2b (and…-8b).

Kinjal Basu, Ibrahim Abdelaziz, Kiran Kate, Mayank Agarwal, Maxwell Crouse, Yara Rizk, Kelsey Bradford, Asim Munawar, Sadhana Kumaravel, Saurabh Goyal, Xin Wang, Luis A. Lastras, Pavan Kapanipathi. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

In this paper, we take a step towards jointly modeling automatic speech recognition (STT) and speech synthesis (TTS) in a fully non-autoregressive way. We develop a novel multimodal framework capable of handling the speech and text modalities as input either individually or together. The proposed model can also be trained with unpaired speech or text data owing to its multimodal nature. We further propose an iterative refinement strategy to improve the STT and TTS performance of our model such that the partial hypothesis at the output can be fed back to the input of our model, thus iteratively improving both STT and TTS predictions. We show that our joint model can effectively perform both STT and TTS tasks, outperforming the STT-specific baseline in all tasks and performing competitively with the TTS-specific baseline across a wide range of evaluation metrics.

Low-Rank Adaptation (LoRA) has emerged as a highly efficient framework for finetuning the weights of large foundation models, and has become the go-to method for data-driven customization of LLMs. Despite the promise of highly customized behaviors and capabilities, switching between relevant LoRAs in a multiturn setting is inefficient, as the key-value (KV) cache of the entire turn history must be recomputed with the LoRA weights before generation can begin. To address this problem, we propose Activated LoRA (aLoRA), an adapter architecture which modifies the LoRA framework to only adapt weights for the tokens in the sequence after the aLoRA is invoked. This change crucially allows aLoRA to accept the base model's KV cache of the input string, meaning that aLoRA can be instantly activated whenever needed in a chain without recomputing the prior keys and values. This enables building what we call intrinsics, i.e. specialized models invoked to perform well-defined operations on portions of an input chain or conversation that otherwise uses the base model by default. We train a set of aLoRA-based intrinsics models, demonstrating competitive accuracy with standard LoRA while significantly improving inference efficiency. We contributed our Activated LoRA implementation to the Huggingface PEFT library.

Kinjal Basu, Ibrahim Abdelaziz, Subhajit Chaudhury, Soham Dan, Maxwell Crouse, Asim Munawar, Vernon Austel, Sadhana Kumaravel, Vinod Muthusamy, Pavan Kapanipathi, Luis Lastras. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

A major concern in using deep learning based generative models for document-grounded dialogs is the potential generation of responses that are not faithful to the underlying document.Existing automated metrics used for evaluating the faithfulness of response with respect to the grounding document measure the degree of similarity between the generated response and the document's content.However, these automated metrics are far from being well aligned with human judgments.Therefore, to improve the measurement of faithfulness, we propose a new metric that utilizes (Conditional) Point-wise Mutual Information (PMI) between the generated response and the source document, conditioned on the dialogue.PMI quantifies the extent to which the document influences the generated response -with a higher PMI indicating a more faithful response.We build upon this idea to create a new decoding technique that incorporates PMI into the response generation process to predict more faithful responses.Our experiments on the BEGIN benchmark demonstrate an improved correlation of our metric with human evaluation.We also show that our decoding technique is effective in generating more faithful responses when compared to standard decoding techniques on a set of publicly available document-grounded dialog datasets.

Collecting data for training dialog systems can be extremely expensive due to the involvement of human participants and the need for extensive annotation.Especially in documentgrounded dialog systems, human experts need to carefully read the unstructured documents to answer the users' questions.As a result, existing document-grounded dialog datasets are relatively small-scale and obstruct the effective training of dialogue systems.In this paper, we propose an automatic data augmentation technique grounded on documents through a generative dialogue model.The dialogue model consists of a user bot and agent bot that can synthesize diverse dialogues given an input document, which are then used to train a downstream model.When supplementing the original dataset, our method achieves significant improvement over traditional data augmentation methods.We also achieve competitive performance in the low-resource setting.

Conversational agents, or chatbots, are widely used to provide customer care and other informational support. Currently, the development of chatbots using standard frameworks requires a lot of manual crafting by subject matter experts (SMEs). On the other hand, while learning-based approaches to dialog have made significant advancements, they require training with a large volume of dialog data, which chatbot developers typically do not have access to. To tackle these challenges, we introduce DOC2BOT, a system that supports the automated construction of chatbots by digesting various forms of documents such as business manuals, HowTos, and customer support pages that organizations own. In addition to that, DOC2BOT provides a user-friendly experience to SMEs, and to minimize their effort by supporting intuitive interactions and streamlining their workflow.

Hui Wan, Song Feng, Chulaka Gunasekara, Siva Sankalp Patel, Sachindra Joshi, Luis Lastras. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2021.

This paper introduces the Eighth Dialog System Technology Challenge. In line with recent challenges, the eighth edition focuses on applying end-to-end dialog technologies in a pragmatic way for multi-domain task-completion, noetic response selection, audio visual scene-aware dialog, and schema-guided dialog state tracking tasks. This paper describes the task definition, provided datasets, baselines and evaluation set-up for each track. We also summarize the results of the submitted systems to highlight the overall trends of the state-of-the-art technologies for the tasks.

We introduce Doc2Dial, an end-to-end framework for generating conversational data grounded in given documents. It takes the documents as input and generates the pipelined tasks for obtaining the annotations specifically for producing the simulated dialog flows. Then, the dialog flows are used to guide the collection of the utterances via the integrated crowdsourcing tool. The outcomes include the human-human dialogue data grounded in the given documents, as well as various types of automatically or human labeled annotations that help ensure the quality of the dialog data with the flexibility to (re)composite dialogues. We expect such data can facilitate building automated dialogue agents for goal-oriented tasks. We demonstrate Doc2Dial system with the various domain documents for customer care.

Implicit relation classification onPenn Discourse TreeBank (PDTB) 2.0 is a common benchmark task for evaluating the understanding of discourse relations.However, the lack of consistency in preprocessing and evaluation poses challenges to fair comparison of results in the literature.In this work, we highlight these inconsistencies and propose an improved evaluation protocol.Paired with this protocol, we report strong baseline results from pretrained sentence encoders, which set the new state-of-the-art for PDTB 2.0.Furthermore, this work is the first to explore fine-grained relation classification on PDTB 3.0.We expect our work to serve as a point of comparison for future work, and also as an initiative to discuss models of larger context and possible data augmentations for downstream transferability.

We introduce doc2dial, a new dataset of goal-oriented dialogues that are grounded in the associated documents.Inspired by how the authors compose documents for guiding end users, we first construct dialogue flows based on the content elements that corresponds to higher-level relations across text sections as well as lower-level relations between discourse units within a section.Then we present these dialogue flows to crowd contributors to create conversational utterances.The dataset includes over 4500 annotated conversations with an average of 14 turns that are grounded in over 450 documents from four domains.Compared to the prior document-grounded dialogue datasets, this dataset covers a variety of dialogue scenes in information-seeking conversations.For evaluating the versatility of the dataset, we introduce multiple dialogue modeling tasks and present baseline approaches.

Jatin Ganhotra, Haggai Roitman, Doron Cohen, Nathaniel Mills, Chulaka Gunasekara, Yosi Mass, Sachindra Joshi, Luis Lastras, David Konopnicki. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). 2020.

An essential component of spoken language understanding (SLU) is slot filling: representing the meaning of a spoken utterance using semantic entity labels. In this paper, we develop end-to-end (E2E) spoken language understanding systems that directly convert speech input to semantic entities and investigate if these E2E SLU models can be trained solely on semantic entity annotations without word-for-word transcripts. Training such models is very useful as they can drastically reduce the cost of data collection. We created two types of such speech-to-entities models, a CTC model and an attention-based encoder-decoder model, by adapting models trained originally for speech recognition. Given that our experiments involve speech input, these systems need to recognize both the entity label and words representing the entity value correctly. For our speech-to-entities experiments on the ATIS corpus, both the CTC and attention models showed impressive ability to skip non-entity words: there was little degradation when trained on just entities versus full transcripts. We also explored the scenario where the entities are in an order not necessarily related to spoken order in the utterance. With its ability to do re-ordering, the attention model did remarkably well, achieving only about 2% degradation in speech-to-bag-of-entities F1 score.

The state of the art in automated conversational agents for enterprise (e.g. for customer support) require a lengthy design process with experts in the loop who have to figure out and specify complex conversation patterns. This demonstration looks at a prototype interface that aims to bring down the expertise required to design such agents as well as the time taken to do so. Specifically, we will focus on how a metawriter can assist the domain-writer during the design process and how complex conversation patterns can be derived from simplifying abstractions at the interface level.

The “Cognitive Master Teacher” is a result of discussions with teachers, members of educational institutions, government bodies and other thought leaders in the United States who have helped us shape its the requirements. It is conceived as a cloud-based and mobile-accessible personal agent that is readily available for teachers to use at anytime and assist them with various issues related to day-to-day teaching activities as well as professional development.

A number of modern storage technologies, when written to, exhibit substantial variability in the outcome of a write action. It is possible to mitigate the effect of the write uncertainty through the use of a feedback loop that rewrites the memory whenever judged necessary, in effect reshaping the write noise. This scheme highlights a tradeoff between the storage capacity of the memory and the cost of writing to it, measured for example in the number of rewrites. We have developed the model of a rewritable channel to provide an explicit form for this tradeoff and study other performance characteristics of such memories. In this paper, we describe some initial results on the information-theoretic analysis of the rewritable channel. We first consider the problem of determining the capacity of this channel with input cost constraints, and obtain a variety of results from which we extract insights that we believe are of value to memory designers. Our results include an upper bound on capacity of the form log (Γκ), where Γ is a constant that can be easily calculated from the channel's statistics and κ is an average cost parameter. We also provide a lower bound on capacity with a similar form. We analyze the particular case of uniform write noise in detail, obtaining a closed form expression for the capacity-cost tradeoff for all possible cost parameters. We explore this formula from the capacity per unit cost perspective and establish that in order to achieve optimal energy and memory-wear per bit, it is sometimes strictly better to take advantage of the rewriting capability as opposed to writing only once; this observation has significant practical implications. We also include a discussion of the relevance of our work to real emerging memory technologies.

Phase Change Memory (PCM) is a promising technology for building future main memory systems. A prominent characteristic of PCM is that it has write latency much higher than read latency. Servicing such slow writes causes significant contention for read requests. For our baseline PCM system, the slow writes increase the effective read latency by almost 2X, causing significant performance degradation. This paper alleviates the problem of slow writes by exploiting the fundamental property of PCM devices that writes are slow only in one direction (SET operation) and are almost as fast as reads in the other direction (RESET operation). Therefore, a write operation to a line in which all memory cells have been SET prior to the write, will incur much lower latency. We propose PreSET, an architectural technique that leverages this property to pro-actively SET all the bits in a given memory line well in advance of the anticipated write to that memory line. Our proposed design initiates a PreSET request for a memory line as soon as that line becomes dirty in the cache, thereby allowing a large window of time for the PreSET operation to complete. Our evaluations show that PreSET is more effective and incurs lower storage overhead than previously proposed write cancellation techniques. We also describe static and dynamic throttling schemes to limit the rate of PreSET operations. Our proposal reduces effective read latency from 982 cycles to 594 cycles and increases system performance by 34%, while improving the energy-delay-product by 25%.

We introduce a technique for constructing codes for bursts of errors that have some known structure; for example bursts of length at most b and Hamming weight at most t. This technique is based on modifying existing codes for generic bursts by replacing a portion of their check matrix with a more efficient one, in light of the additional constraints on the burst. We illustrate this procedure by modifying the Fire, Burton and Gilbert codes to address bursts with maximum Hamming weight, bursts with solid errors, or bursts with internal “mini-bursts”. We provide evidence that the redundancy of the codes we construct can be very good through examples, one of which is optimal within the class of cyclic codes.

Many storage channels admit reading and rewriting of the content at a given cost. We consider rewritable channels with uniform write noise and a hidden state which models the unknown characteristics of the memory cell. In addition to mitigating the effect of the write noise, rewrites can help the write controller obtain a better estimate of the hidden state. We present two coding strategies, each of which yields a lower bound on the rewrite capacity. We show that the second strategy is asymptotically optimal as the number of rewrites gets large.

Phase Change Memory (PCM) may become a viable alternative for the design of main memory systems in the next few years. However PCM suffers from limited write endurance. Therefore future adoption of PCM as a technology for main memory will depend on the availability of practical solutions for wear leveling that avoids uneven usage especially in the presence of potentially malicious users. First generation wear leveling algorithms were designed for typical workloads and have significantly reduced lifetime under malicious access patterns that try to write to the same line continuously. Secure wear leveling algorithms were recently proposed. They can handle such malicious attacks, but require that wear leveling is done at a rate that is orders of magnitude higher than what is sufficient for typical applications, thereby incurring significantly high write overhead, potentially impairing overall performance system. This paper proposes a practical wear-leveling framework that can provide years of lifetime under attacks while still incurring negligible (<;1%) write overhead for typical applications. It uses a simple and novel Online Attack Detector circuit to adapt the rate of wear leveling depending on the properties of the memory reference stream, thereby obtaining the best of both worlds - low overhead for typical applications and years of lifetime under attacks. The proposed attack detector requires a storage overhead of 68 bytes, is effective at estimating the severity of attacks, is applicable to a wide variety of wear leveling algorithms, and reduces the write overhead of several recently proposed wear leveling algorithms by 16x-128x. The paradigm of online attack detection enables other preventive actions as well.

Phase Change Memory (PCM) is emerging as a promising technology to build large-scale main memory systems in a cost-effective manner. A characteristic of PCM is that it has write latency much higher than read latency. A higher write latency can typically be tolerated using buffers. However, once a write request is scheduled for service to a bank, it can still cause increased latency for later arriving read requests to the same bank. We show that for the baseline PCM system with read-priority scheduling, the write requests increase the effective read latency to 2.3x (on average), causing significant performance degradation. To reduce the read latency of PCM devices under such scenarios, we propose adaptive Write Cancellation policies. Such policies can abort the processing of a scheduled write requests if a read request arrives to the same bank within a predetermined period. We also propose Write Pausing, which exploits the iterative write algorithms used in PCM to pause at the end of each write iteration to service any pending reads. For the baseline system, the proposed technique removes 75% of the latency increase incurred by read requests and improves overall system performance by 46% (on average), while requiring negligible hardware and simple extensions to PCM controller.

We introduce a simple communication-theoretic model for phase-change memory (PCM), based on empirical observations. Our modeling effort is focused on capturing the effects of resistance drift, which is believed to be one of the major obstacles to achieving high bit/cell densities in PCM. The model is used to estimate how the information theoretic storage capacity of PCM evolves as the time gap between a write and its subsequent read widens. We use our model to evaluate the performance of simple modulation and detection schemes, also considering the use of trellis coded modulation (TCM). Our evaluation of these strategies shows that the use of TCM provides several benefits, including a significant increase in retention time, i.e., the expected maximum amount of storage time before which the stored data can be reliably retrieved.

We consider the problem of information storage in multilevel heterogeneous memories, where different cells can support different data level-sets. Such heterogeneity arises due to variability in the physical cell characteristics in emerging technologies such as Phase Change Memory (PCM) technology, which is our specific motivation. We show that the heterogeneous memory problem can be formulated in terms of the information-theoretic `Channel Coding with Side-Information at Transmitter' (CSIT) paradigm. We present a binary decomposition of the problem, and show that this decomposition allows for simple binary code constructions. We discuss one such code-construction based on binary Luby Transform (LT) code matrices. We present simulation results using cell variability data collected from a PCM test array, and show that the proposed approach can yield a significant advantage in storage capacity.

Phase Change Memory (PCM) is emerging as a scalable and power efficient technology to architect future main memory systems. The scalability of PCM is enhanced by the property that PCM devices can store multiple bits per cell. While such Multi-Level Cell (MLC) devices can offer high density, this benefit comes at the expense of increased read latency, which can cause significant performance degradation. This paper proposes Morphable Memory System (MMS), a robust architecture for efficiently incorporating MLC PCM devices in main memory. MMS is based on observation that memory requirement varies between workloads, and systems are typically over-provisioned in terms of memory capacity. So, during a phase of low memory usage, some of the MLC devices can be operated at fewer bits per cell to obtain lower latency. When the workload requires full memory capacity, these devices can be restored to high density MLC operation to have full main-memory capacity. We provide the runtime monitors, the hardware-OS interface, and the detailed mechanism for implementing MMS. Our evaluations on an 8-core 8GB MLC PCM-based system show that MMS provides, on average, low latency access for 95% of all memory requests, thereby improving overall system performance by 40%.

We present a closed form expression for the capacity of the uniform noise rewritable channel with average write cost and a constraint on the input range. We show the existence of a critical cost κ0such that for all costs κ ≥ κ0, the capacity/cost tradeoff is given by an offset added to the logarithm of the cost. Assuming κ0> 1, for 1 ≤ κ0the capacity/cost tradeoff grows faster than a logarithm.

We study binary Content Addressable Memories (CAMs) that employ a resistive element to store content. A CAM has a match line for every word stored which is sensed in order to determine a match/no match condition. We show how simple, low redundancy coding techniques can dramatically improve the ability to differentiate a match from a mismatch, effectively allowing a CAM design that stores nearly twice as many bits in the same memory as a competing design that stores each bit and its complement. The theory of coding for asymmetric errors is relevant in this problem; we rely on it to prove that ⌊n/2⌋ out of n constant weight codes are optimal for sensing.

We present a class of algorithms for encoding data in memories with stuck cells. These algorithms rely on earlier code constructions termed cyclic Partitioned Linear Block Codes. For the corresponding q-ary BCH-like codes for u stucks in a codeword of length n, our encoding algorithm has complexity O((u logqn)2) Fqoperations, which we will show compares favorably to a generic approach based on Gaussian elimination. The computational complexity improvements are realized by taking advantage of the algebraic structure of cyclic codes for stucks. The algorithms are also applicable to cyclic codes for both stucks and errors.

We consider storage channels that admit optional reading and rewriting of the content at a given cost. This is a general class of channels that models many nonvolatile memories. We present recent results on such rewritable channels with constraints on both the maximum and the average number of atomic rewrite iterations. We derive a general lower capacity bound for rewritable storage channels impaired by additive noise. For the special case of uniform noise, we present tight upper and lower capacity bounds and suggest some capacity-achieving coding techniques.

The block erase requirement in NAND Flash devices leads to the need for garbage collection. Garbage collection results in write amplification, that is, to an increase in the number of physical page programming operations. Write amplification adversely impacts the limited lifetime of a NAND Flash device, and can add significant system overhead unless a large spare factor is maintained. This paper proposes a NAND Flash system which uses multi-write coding to reduce write amplification. Multi-write coding allows a NAND Flash page to be written more than once without requiring an intervening block erase. We present a novel two-write coding technique based on enumerative coding, which achieves linear coding rates with low computational complexity. The proposed technique also seeks to minimize memory wear by reducing the number of programmed cells per page write. We describe a system which uses lossless data compression in conjunction with multi-write coding, and show through simulations that the proposed system has significantly reduced write amplification and memory wear.

We present some recent results on rewritable channels, that is, storage channels that admit optional reading and rewriting of the content at a given cost. This is a general class of channels that models many nonvolatile memories. We focus on the storage capacity of rewritable channels affected by data-dependent noise. We prove tight upper and lower bounds on the storage capacity of a simple yet significant channel model and suggest some simple capacity-achieving coding techniques. Lower bounds on the storage capacity of Gaussian rewritable channels with data-dependent noise are also shown.

We study memories capable of storing multiple bits per memory cell, with the property that certain state transitions “wear” the cell. We introduce a model that is relevant for Phase Change Memory, a promising emerging nonvolatile memory technology that exhibits limitations in the number of particular write actions that one may apply to a cell before rendering it unusable. We exploit the theory of Write Efficient Memories to derive a closed form expression for the storage capacity/lifetime fundamental tradeoff for this model. We then present families of codes specialized to distinct ranges for the target lifetimes, covering the full range from moderate redundancy to an arbitrarily large lifetime increase. These codes have low implementation complexity and remarkably good performance; for example in an 8 level cell we can increase the lifetime of a memory by a factor of ten while sacrificing only 2/3 of the uncoded storage capacity of the memory.

Phase Change Memory (PCM) is an emerging memory technology that can increase main memory capacity in a cost-effective and power-efficient manner. However, PCM cells can endure only a maximum of 107 - 108 writes, making a PCM based system have a lifetime of only a few years under ideal conditions. Furthermore, we show that non-uniformity in writes to different cells reduces the achievable lifetime of PCM system by 20x. Writes to PCM cells can be made uniform with Wear-Leveling. Unfortunately, existing wear-leveling techniques require large storage tables and indirection, resulting in significant area and latency overheads.

In this paper, it is shown that each Slepian-Wolf coding problem is related to a dual channel coding problem in the sense that the sphere packing exponents, random coding exponents, and correct decoding exponents in these two problems are mirror-symmetrical to each other. This mirror symmetry is interpreted as a manifestation of the linear codebook-level duality between Slepian-Wolf coding and channel coding. Furthermore, this duality, in conjunction with a systematic analysis of the expurgated exponents, reveals that nonlinear Slepian-Wolf codes can strictly outperform linear Slepian-Wolf codes in terms of rate-error tradeoff at high rates. The linear codebook-level duality is also established for general sources and channels.

In this paper, the redundancy of both variable and fixed rate Slepian–Wolf coding is considered. Given any jointly memoryless source-side information pair$\{(X_i, Y_i)\}_{i=1}^{\infty}$with finite alphabet, the redundancy$R^n(\epsilon_n)$of variable rate Slepian–Wolf coding of$X_1^n$with decoder only side information$Y_1^n$depends on both the block length$n$and the decoding block error probability$\epsilon_n$, and is defined as the difference between the minimum average compression rate of order$n$variable rate Slepian–Wolf codes having the decoding block error probability less than or equal to$\epsilon_n$, and the conditional entropy$H(X\vert Y)$, where$H(X\vert Y)$is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian–Wolf coding of$X_1^n$with decoder only side information$Y_1^n$is defined similarly and denoted by$R^n_F(\epsilon_n)$. It is proved that under mild assumptions about$\epsilon_n,$$R^n(\epsilon_n) = d_v \sqrt{-\log\epsilon_n/n} + o(\sqrt{-\log \epsilon_n/n})$and$R^n_{F}(\epsilon_n) = d_f \sqrt{- \log \epsilon_n / n} + o(\sqrt{-\log \epsilon_n/n})$, where$d_f$and$d_v$are two constants completely determined by the joint distribution of the source-side information pair. Since$d_v$is generally smaller than$d_f$, our results show that variable rate Slepian–Wolf coding is indeed more efficient than fixed rate Slepian–Wolf coding.

Lower and upper bounds on the reliability region of universal variable-rate Slepian-Wolf coding are derived.

We characterize the redundancy-error tradeoff in Slepian-Wolf coding. Similar results are derived for a class of cyclic-symmetric channels. Through the linear codebook-level duality between Slepian-Wolf coding and channel coding, we show that, in Slepian-Wolf coding, linear codes are optimal in terms of redundancy-error tradeoff at rate close to the Slepian-Wolf limit but suboptimal at high rate.

We study memories protected with error control codes, in which the memory's contents are organized in lines which are read and written to in isolation from other lines. In these memories the available redundancy is structured so as to protect individual lines rather than the entire memory as a whole. Often designers wish to read and write only parts of the memory line, as in some instances this leads to various favorable system design tradeoffs, including better power consumption, increased data access concurrency, etc. (alternatively one may say that designers sometimes would prefer smaller line sizes). Nevertheless when designing systems with such subline accesses it is often found that in order to mantain a given level of reliability, the total amount of redundancy allocated in the memory needs to be increased beyond desirable levels. In this work, we initiate a study of the problem of structuring error control codes to allow subline accesses with good tradeoffs between reliability and redundancy. We motivate and explore a setting in which a "double-lookup" protocol is used in conjunction with certain types of two-level codes, whereby error detection is attained in a first level and error correction using the second level is performed whenever errors are detected in the first level. We obtain lower bounds on redundancy for a given level of reliability and offer a code construction that attains this bound for a certain important class of parameters. We also introduce an alternate construction which allows us to find longer codes under restrictions of the Galois field size used in the codes.

The Slepian-Wolf coding problem is often viewed as a channel coding problem for the purpose of gaining insight into its properties. In this perspective, source sequences are associated with balls of side information sequences, and then one packs in each bin as many of these balls as possible with little or no overlap. Alternatively, one can treat the problem as a source coding problem in which for a given side information sequence, the set of conditionally probable source sequences is distributed in as many bins as required by a fidelity criterion. In an earlier series of publications we developed the theory of redundancy of variable rate Slepian-Wolf codes using the first viewpoint. In this work, we obtain similar results from the second viewpoint; this direction has unique technical challenges but also reinforces the fundamental role of our previously introduced notion of intrinsic entropy. In one of our key technical contributions, we use an averaging argument resembling Shannon's random coding idea that we expect will be useful in studying other problems of source coding with side information.

We consider a class of algorithms related to Lempel-Ziv that incorporate restrictions on the manner in which the data can be parsed with the goal of introducing new tradeoffs between implementation complexity and data compression ratios. Our main motivation lies within the field of compressed memory computer systems. Here requirements include extremely fast decompression and compression speeds, adequate compression performance on small data block lengths, and minimal hardware area and energy requirements. We describe the approach and provide experimental data concerning its compression performance with respect to known alternatives. We show that for a variety of data sets stored in a typical main memory, this direction yields results close to those of earlier techniques, but with significantly lower energy consumption at comparable or better area requirements. The technique thus may be of eventual interest for a number of applications requiring high compression bandwidths and efficient hardware implementation.

In this paper we analyze the redundancy of variable rate Slepian-Wolf coding. For any memoryless source-side information pair (X, Y) = {(Xi,Yi)}Einfini=1with finite alphabet, the redundancy Rn(epsin) of variable rate Slepian-Wolf coding is defined as the minimum of the difference between the compression rate of any variable-rate Slepian-Wolf code resulting from coding XEn1with decoding error probability epsin, and the conditional entropy H(X|Y). It is proved that under mild assumptions, for sufficiently large n, Rn(epsin) is lower bounded by dradiclog n/n, where d > 0 is a constant

We investigate the maximum increase in number of phrases that results from changing k consecutive symbols in a string x having length n parsed using an LZ'77-like algorithm. We consider a class of compression algorithms that partition a sequence into a collection y of nonoverlapping, variable-length phrases and encode them. Each phrase either is a singleton or matches a substring that starts to its left. We show that changing a single symbol of x in position i can yield an expansion that is of order O(n-i)/sup 2/3/ as (n-i)/spl rarr//spl infin/. Our lower bound requires an alphabet size of O(n-i)/sup 1/3/. We also show that changing k consecutive symbols starting from position i can yield an expansion having a similar but somewhat more involved form. The paper contains both analytically derived upper and lower bounds, and algorithms for numerically computing tighter bounds. While deriving the bounds, we provide a detailed analysis of how expansion can arise when changing consecutive symbols. This problem is motivated by management policies for computer systems, such as the IBM Memory eXpansion Technology (MXT) or the IBM iSeries compressed disks, that use LZ'77-like coding on small compression units, such as 1-4 kbyte, and store the compressed data in memory or on disk tracks. Here, when a change of a portion of the compression unit occurs, for example, an L2 cache line, or a 512-byte disk sector, the data is recompressed and potentially stored in a different location. Knowing the maximum expansion, rather than the average expansion, is an important factor for designing policies for allocation and management of memory or disk space.

We show that for every$n ≫ 2$the standard$ n$th-order approximation$R_n(D)$, to the rate-distortion function of the binary-symmetric Markov source (BSMS) is not successively refineable under the Hamming distortion measure in an open interval of the form$D_n !≪ ! D !≪ !1/2 ! = !D_max $.

We give a single-letter outer bound for the two-descriptions problem for independent and identically distributed (i.i.d.) sources that is universally close to the El Gamal and Cover (EGC) inner bound. The gaps for the sum and individual rates using a quadratic distortion measure are upper-bounded by 1.5 and 0.5 bits/sample, respectively, and are universal with respect to the source being encoded and the desired distortion levels. Variants of our basic ideas are presented, including upper and lower bounds on the second channel's rate when the first channel's rate is arbitrarily close to the rate-distortion function; these bounds differ, in the limit as the code block length goes to infinity, by not more than 2 bits/sample. An interesting aspect of our methodology is the manner in which the matching single-letter outer bound is obtained, as we eschew common techniques for constructing single-letter bounds in favor of new ideas in the field of rate loss bounds. We expect these techniques to be generally applicable to other settings of interest.

We study the problem of the reconstruction of a Gaussian field defined in [0,1] using N sensors deployed at regular intervals. The goal is to quantify the total data rate required for the reconstruction of the field with a given mean square distortion. We consider a class of two-stage mechanisms which (a) send information to allow the reconstruction of the sensor's samples within sufficient accuracy, and then (b) use these reconstructions to estimate the entire field. To implement the first stage, the heavy correlation between the sensor samples suggests the use of distributed coding schemes to reduce the total rate. Our main contribution is to demonstrate the existence of a distributed block coding scheme that achieves, for a given fidelity criterion for the sensor's measurements, a total information rate that is within a constant, independent of N, of the minimum information rate required by an encoder that has access to all the sensor measurements simultaneously. The constant in general depends on the autocorrelation function of the field and the desired distortion criterion for the sensor samples.

We give a single letter outer bound for the two descriptions problem for iid sources that is universally close to the El Gamal and Cover (EGC) inner bound. The gaps in the quadratic distortion case for the sum and individual rates are upper bounded by 1.5 and 0.5 bits/sample, respectively. These constant bounds are universal with respect to the source being encoded, provided that its variance is finite. They are also universal with respect to the desired distortion levels, under the assumption that, after normalizing the source to have unit variance, D/sub i/ /spl isin/ (0,1) for i /spl isin/ {0,1,2} and D/sub 0/ /spl les/ (D/sub 1//sup -1/ + D/sub 2//sup -1/ - 1)/sup -1/.

We develop explicit, general bounds for the probability that the normalized partial sums of a function of a Markov chain on a general alphabet would exceed the steady-state mean of that function by a given amount. Our bounds combine simple information-theoretic ideas together with techniques from optimization and some fairly elementary tools from analysis. In one direction, we obtain a general bound for the important class of Doeblin chains; this bound is optimal, in the sense that in the special case of independent and identically distributed random variables it essentially reduces to the classical Hoeffding bound. In another direction, motivated by important problems in simulation, we develop a series of bounds in a form which is particularly suited to these problems, and which apply to the more general class of "geometrically ergodic" Markov chains

This paper investigates the maximum increase in number of phrases that results from changing one symbol in a string that has been parsed using an LZ'77-like algorithm. We provide upper and lower bounds to the maximum expansion as a function of the position of the changed symbol and of the string length.

This paper derives a number of pathwise results related to the sliding window Lempel-Ziv (SWLZ) algorithm, including an upper bound on the redundancy and reasonably tight upper and lower bounds for the number of bits spent on the encoding of the phrase lengths. We also investigate important basic properties of the various limits involved in this study; for example, we succeed in demonstrating that for sources that have exponential rates for entropy and for any database length, the limiting average number of phrases per symbol exists and is constant with probability one.

For a stationary, irreducible and aperiodic Markov chain with finite alphabet A, starting symbol X/sub 0/=/spl sigma/, transition probability matrix P, stationary distribution /spl pi/, support S(/spl pi/,P)={(j,k):/spl pi//sub j/P/sub k|j/>0} and for a function f such that M=/spl Delta/E/sub /spl pi/P/f(X/sub 1/,X/sub 2/)0/{K/sub n//(1+K/sub n/)}/spl epsiv//(max/sub j,k:P(k|j)/>0|f(j,k)|]/sup 2/ where K/sub n/=(1-|A|max/sub j,k/|P/sub k|j//sup n/-/spl pi//sub k/)/n). Under the conditions stated, the set over which the sup is taken is nonempty and therefore the sup exists and is positive; it is also shown that the sup is attained at a finite value of n. A nonasymptotic version of this result is also given based on the method of Markov types.

Given an achievable quadruple (R/sub 1/, R/sub 2/, D/sub 1/, D/sub 2/) for progressive transmission, the rate loss at step i is defined as L/sub i/=R/sub i/-R(D/sub i/). Let D/sub 1/ and D/sub 2/ be any two desired distortion levels (D/sub 2/