jump to navigation

Review: The Theory of Information and Coding January 25, 2012

Posted by flashbuzzer in Research.
Tags: , , , ,
add a comment

I recently finished “The Theory of Information and Coding” by R.J. McEliece. I originally used this book for a course taught by Dr. McEliece in the Fall 2002-03 quarter.

This book has one review on Amazon, so I hope to provide some additional insights for people who are considering obtaining the book.

In this book, the author provides the reader with a basic understanding of the fields of information theory and coding theory. He begins by presenting the concepts of entropy and mutual information, which are central to information theory. With these fundamental definitions in hand, he then presents the two main results of this area – Shannon’s channel coding and source coding theorems. After extending these results to the Gaussian case, he unifies them via a proof of the source-channel coding theorem. He then shifts gears and focuses on coding theory. He introduces several important types of codes, including linear codes – and some of their sub-classes, including cyclic codes, BCH codes and Reed-Solomon codes. The rest of the book contains a brief overview of convolutional codes and a discussion of variable-length source codes.

The author skillfully guides the reader through the information theory section of the text. By way of comparison, I had also read through one of the major texts in this area, Elements of Information Theory by Cover and Thomas; I found McEliece’s presentation of the fundamental information-theoretic concepts and results to be simpler and more intuitive. The author uses simple examples throughout the text to drive home key ideas; for example, he repeatedly discusses the (7,4) Hamming code – which happens to be a superb teaching tool. I also derived valuable insights from the presentation of the BCH decoding algorithm and the rigorous explanation of the efficacy of Huffman’s algorithm. In addition, I enjoyed the anecdotes that the author sprinkles throughout the text, as many of them arise from his long-standing association with JPL; thus, they bridge the gap between theory and practice.

My main issue with the text stems from the relatively large number of typos that I discovered. This is somewhat disappointing, as I read through its second edition. Also, the chapter on convolutional codes seems to be, technically speaking, rather light. This causes the section on coding theory to seem unbalanced, as the author skillfully presents many technical results that underlie the area of block coding. I would have preferred that the author extend the book to provide a more comprehensive treatment of convolutional codes, especially since they are more widely used in practice compared to block codes.

Overall I would strongly recommend this book to those who want a gentle introduction to the linked fields of information theory and coding theory.

Advertisements

Review: Finite Fields for Computer Scientists and Engineers June 17, 2011

Posted by flashbuzzer in Research.
Tags: , , ,
add a comment

I recently finished “Finite Fields for Computer Scientists and Engineers” by R.J. McEliece. I originally used this book for a course taught by Dr. McEliece in the Winter 2002-03 quarter.

This book has two reviews on Amazon, so I hope to provide some additional insights for people who are considering obtaining the book.

In this book, the author presents the theory of finite fields with an eye towards their application in the design of communication systems. He begins by introducing the concept of a Euclidean domain along with the familiar – yet vital – construct of Euclid’s algorithm, which he then uses to show how primes can be uniquely factored in a Euclidean domain. With these results in hand, he shows how Euclidean domains can be used to construct fields, which forms a nice transition to the book’s core material: a discussion of the properties of finite fields, including existence and uniqueness, and how these properties can be used to factor polynomials over these fields. The rest of the book forms a set of advanced topics that draw on these fundamental concepts, including

  • the notion of the trace (relative to a subfield)
  • properties of linear recurrences over finite fields
  • the fundamentals of m-sequences and their cross-correlation properties.

The author skillfully motivates and presents the central results of this book. Indeed, his self-deprecating writing style triggered many fond memories from my days as an undergrad, as I took three courses from him. Somehow the author pulls off the difficult balancing act of presenting mathematically challenging material without truly sacrificing mathematical rigor, which is quite remarkable. The book also contains several fascinating concepts that I enjoyed learning, including Euler’s phi function, the Mobius inversion formula and the Chevalley-Warning theorem.

One aspect of the book that I did find to be a bit bothersome, though, was that each chapter was not divided into separate sections. In my opinion, this would have improved the flow of the book and provided many helpful “signposts” for the reader, especially while studying a rather lengthy chapter. More often than not I would be shown a result, eventually understand the proof, and then be unsure as to its importance in the context of the chapter in question.

Overall I would strongly recommend this book to those who want a gentle introduction to finite fields while gaining a healthy appreciation for their theoretical underpinnings.

Review: Space-Time Block Coding for Wireless Communications December 19, 2010

Posted by flashbuzzer in Research.
Tags: , , ,
add a comment

I recently finished Space-Time Block Coding for Wireless Communications by E.G. Larsson and P. Stoica. I originally used this book for a course taught by my advisor in the Fall 2005 semester.

This book only has one review on Amazon, so I hope that my thoughts will be useful for people who are considering obtaining the book.

In this book, the authors introduce the fundamental concepts of multi-input multi-output (MIMO) wireless communications and space-time block coding (STBC), and they show how STBC can significantly improve the performance of MIMO systems in many ways. They begin by presenting the tools that are necessary for a thorough understanding of MIMO systems, including channel modeling, information theory and error probability analysis. They then recap the familiar concept of receive diversity and use it to motivate the breakthrough concept of transmit diversity, which leads to the introduction of STBC. The rest of the book is a compendium of advanced topics for STBC, including coding for ISI channels, the design of coherent/non-coherent STBC receivers, coding for transmitters with partial/full CSI, and coding in the presence of interference.

The authors do a fantastic job of presenting and teaching fundamental concepts to the reader. A painstaking amount of effort is made to hammer home key points and build the right level of intuition. In particular, the authors set the tone for the remainder of the book in Chapter 1 by presenting a simple example that considers 2×1 and 1×2 systems; moreover, the book contains numerous examples of systems that employ one or two transmit/receive antennas, which is invaluable in terms of enhancing the learning process. The book is also well-organized; to wit, the authors present several theorems and results in Chapters 4 (“Error Probability Analysis”) and 7 (“Linear STBC for Flat Fading Channels”). By constantly referring to results in these two chapters, it is clear that they are meant to serve as a focal point for understanding the rest of the book. In addition, the authors have put a great deal of effort into generating performance plots; they are properly labeled, and the various curves in each plot are easy to distinguish.

It should be noted that the authors engage in some degree of self-promotion in the book, especially in the latter chapters (9-11); in my view, this detracts (albeit slightly) from its quality. Now it should also be noted that such self-promotion is difficult to avoid, especially when discussing a (relatively) nascent research area in which the authors have obtained many of the major results. A more balanced approach to describing these concepts would have been in order, though. In particular, the authors should have more fully elucidated the drawbacks of using OSTBC in MIMO systems, in order to not perpetuate the impression that OSTBC are the “best choice” in terms of transmit-side strategies. Also, the book has only four errata listed on this page, though I am quite certain that the book has more than four errata. In addition, the book relies heavily on a thorough understanding of matrix analysis; at this point I’m not aware of a good textbook on that topic, though. For those who would cite the text by Horn and Johnson, my thought is that it is more of a reference book than an actual teaching tool.

Overall I would strongly recommend this book to those who want to gain a more solid understanding of MIMO systems and the role that STBC can play in terms of improving their performance.

An Energy-Based Comparison of Long-Hop and Short-Hop Routing in MIMO Networks May 31, 2010

Posted by flashbuzzer in Research.
Tags: ,
add a comment

My fifth journal paper appeared in the IEEE Transactions on Vehicular Technology last January. You can find a pre-print on arXiv here.

Here are my thoughts on this paper’s strengths and weaknesses.

Strengths: In this paper, we compared long-hop routing and short-hop routing in a multi-antenna wireless network, where the metric of interest was the end-to-end transmission energy. Using tools from stochastic geometry and large-antenna analysis, we were able to show the energy advantage of short-hop routing in three limiting scenarios. We also considered a more practical delay-constrained scenario and showed the asymptotic advantage of long-hop routing in that case. To the best of our knowledge, this was the first theoretical study to compare hop length-based routing strategies in a MIMO network.

Weaknesses: Unfortunately, the practicality of our work was limited by the fact that we only obtained asymptotic results; for example, we considered cases where the number of transmit/receive antennas and the hop-count grew large. This was primarily due to our decision to consider a MIMO network, as the pertinent mathematical expressions were much more unwieldy than their single-antenna counterparts. Also, I was only able to obtain results for networks where the nodes were randomly distributed according to a Poisson point process. My lack of familiarity with stochastic geometry prevented me from extending our results to a much larger, and potentially more interesting, class of networks.

This was my fourth accepted IEEE journal paper and nicely capped off my graduate school career. I should also note that this paper was initially submitted to the IEEE JSAC special issue on stochastic geometry. It was justly rejected for being sparse in terms of its stochastic geometry-related contributions, but the reviewers and the AE, Martin Haenggi, offered critical comments that helped me in preparing it for re-submission to the IEEE TVT. The TVT reviewers and the AE, Mischa Dohler, also offered various comments and suggestions that greatly improved the manuscript.

Relay-Assisted User Scheduling in Wireless Networks with Hybrid-ARQ February 1, 2010

Posted by flashbuzzer in Research.
Tags: ,
add a comment

My fourth journal paper appeared in the IEEE Transactions on Vehicular Technology last November. You can find a pre-print on arXiv here.

Here are my thoughts on this paper’s strengths and weaknesses.

Strengths: In this paper, we considered the problem of downlink user scheduling and asked the following question: how should scheduling be performed under a hybrid-ARQ transmission framework, given that at least one relay is available to assist the base station? For two distinct cost models, we proved that the optimal scheduler was a priority-index policy, where the assisting relay must be considered when computing each user’s priority index. This paper illustrates the power of relay selection in yet another aspect of wireless system design.

Weaknesses: This paper was also the outcome of my attempt to understand the well-studied, yet mathematically interesting area of queuing and scheduling. My brief foray into this area showed me that I needed to build my foundation in Markov chains in order to do serious research. Unfortunately, I was only able to obtain the above stated result, which was a relatively simple extension of some previous work by J. Huang et al.

This was my third accepted IEEE journal paper, though it was technically a correspondence (as opposed to a regular paper). I do want to commend the anonymous reviewers, who rightly observed that the initially submitted manuscript was too long and contained many trivial results. The outcome of the review process was a more polished paper that was also of an appropriate length.

Review: Introduction to Space-Time Wireless Communications January 25, 2010

Posted by flashbuzzer in Research.
Tags: , ,
add a comment

I recently finished Introduction to Space-Time Wireless Communications by A. Paulraj, R. Nabar and D. Gore. I originally used this book for a course taught by my advisor in the Fall 2005 semester. On a (possibly) related note, savvy Internet denizens will discover that Paulraj is my “academic grandfather.”

This book has already been reviewed (some would say “thoroughly castigated”) on Amazon, so I’ll just contribute some of my observations and hope that they provide some additional data points for people who are considering obtaining the book.

I had a conversation regarding this book with one of my former research group-mates that proved to be enlightening. He encouraged me to re-read the preface, where the authors state, “this area of technology has grown so large in the past few years that this book cannot cover all aspects in moderate detail. Rather, our aim has been to provide a coherent overview of the key advances in this field emphasizing basic theory and intuition. We have attempted to keep the presentation as simple as possible without sacrificing accuracy.”

When I viewed the book in this light, I was able to tolerate the first eight chapters, which appear to be (mostly) presented at the stated level of detail. In those first eight chapters, the authors do a reasonable job of presenting (without much in the way of rigorous proofs, as expected) fundamental concepts including space-time channel modeling, space-time channel capacity and space-time coding. They even cover a somewhat advanced topic, transmit-side precoding, at a reasonable level.

In my opinion, the book really “goes off the rails” in the last four chapters, which make a half-hearted attempt at presenting more advanced topics including MIMO-OFDM, the MIMO MAC/BC channels and the (much celebrated) diversity-multiplexing tradeoff. Unfortunately, this degrades the cohesion of the book and even left me with a sour taste in my mouth as I finished the last section. Various results were presented without even a modicum of intuition or insight, including the entire chapter on space-time co-channel interference mitigation, which suffered from lazy and uninspired writing (note that interference is a critical issue in multi-antenna wireless networks).

Overall, I would recommend this book to “graduate students in wireless communications” and “wireless designers in industry” (as noted in the text) with the following caveats. Readers would be advised to focus only on the first eight chapters and become familiar with their basic results. After achieving this goal, they should employ a variety of methods to gain deep intuition and insight on all of the material in the text, including reading through the relevant references, attempting to re-derive the key results, and discussing them with motivated colleagues. For example, I should note that I acquired a much better understanding of the diversity-multiplexing tradeoff after an extensive whiteboard-aided discussion with one of my former research group-mates.

Perhaps a more hard-hitting (and well-written) book on space-time wireless communications is in the works (heh heh).

Relay Subset Selection in Wireless Networks Using Partial Decode-and-Forward Transmission October 7, 2009

Posted by flashbuzzer in Research.
Tags: ,
add a comment

My third journal paper appeared in the IEEE Transactions on Vehicular Technology last February. You can find a pre-print on arXiv here.

Here are my thoughts on this paper’s strengths and weaknesses.

Strengths: In this paper, we used a simple theoretical model to obtain some practical insights. Specifically, we considered the relay selection problem given that all of the candidate relays employ a partial decode-and-forward strategy. Assuming that the network is static, we showed that the ergodic rate can be maximized by placing all of the candidate relays at a single point. This is intuitively satisfying, as intelligent node placement is essential when initially setting up a wireless network. Also, we were able to use neat mathematical tools such as diversity gain and generalized diversity gain to characterize the performance of relay selection under this partial decode-and-forward framework.

Weaknesses: Unfortunately, neat theoretical models cannot be used to explain all of the practical scenarios that can be realized. In particular, our model only considered the performance impact of path loss, and so lognormal shadowing was not taken into account. Placing a candidate relay node at the ergodic rate-maximizing point appears to be a good strategy, but what if a large building blocks the line-of-sight path between the candidate relay and the intended destination? Also, as far as I can tell, partial decode-and-forward is not employed in either the IEEE 802.16j or the 3GPP LTE-Advanced standards, which limits the practical scope of our work.

This was my second accepted IEEE journal paper, which was another important milestone in my graduate school career. I should also note that the review process for Trans VT is excellent; in particular, this paper was initially submitted in November 2007, and the final acceptance notice was issued in June 2008. This implies that authors seeking a fast turnaround time for their papers should consider submitting to Trans VT. Much of the credit for the smoothness of the review process should go to Weihua Zhuang, who is the Editor-in-Chief of the Transactions.

The Impact of Channel Feedback on Opportunistic Relay Selection for Hybrid-ARQ in Wireless Networks August 5, 2009

Posted by flashbuzzer in Research.
Tags: ,
add a comment

My second journal paper appeared in the IEEE Transactions on Vehicular Technology last March. You can find a pre-print on arXiv here.

Here are my thoughts on this paper’s strengths and weaknesses.

Strengths: In this paper, we studied a practical problem, namely that of relay selection in a wireless network, and obtained a near-practical solution to this problem. It should be stressed that rate-compatible punctured coding is an important element of industry standards such as IEEE 802.16e and 3GPP LTE. Also, a well-crafted comment from one of the paper’s anonymous reviewers motivated us to thoroughly revise Section 5.1; the results of the revision strengthened our belief in our solution’s near-practicality. In particular, we cited various parameters from the IEEE 802.11a standard to support our assertion that opportunistic relay selection would not significantly increase the level of signaling overhead in a wireless network.

Weaknesses: An inherent limitation to studying a practical problem is the resultant difficulty in obtaining meaningful, closed-form mathematical results. Mathematical elegance is a quality that is rarely attributed to hybrid-ARQ and convolutional coding; combining those two transmission strategies with opportunistic relay selection limited us to the relatively simple analytical results in Section 4. Also, I used an insufficient number of Monte Carlo trials to obtain the simulation results in Sections 5.2 and 5.3. This resulted in plots that would have greatly benefited from either the addition of error bars or additional test runs.

This was my first accepted IEEE journal paper, which was a nice milestone in my graduate school career. I also greatly enjoyed the paper revision process, as it was my first opportunity to mull over reviewer comments and determine how to address them. Formulating a coherent plan for a paper revision is often difficult, but it is well worth the time and effort; for example, I always enjoy reading well-written author responses to my comments whenever I serve as an anonymous reviewer.

Rate Bounds for MIMO Relay Channels May 25, 2009

Posted by flashbuzzer in Research.
Tags: ,
add a comment

My first journal paper appeared in the Journal of Communications and Networks last June. You can find a pre-print on arXiv here.

I thought that I would list some of this paper’s strengths and weaknesses, which may provide some guidance for researchers in the area of wireless communications.

Strengths: We tackled an interesting open problem, which entailed determining the capacity of the full-duplex MIMO relay channel. The end result was a nice technical contribution, where we proposed two partial source-relay cooperation strategies that improved upon a previously proposed lower bound. An inherent advantage in performing information-theoretic research is that reviewers have to be more clever when attempting to reject your submissions, assuming that the stated results are correct. Also, Section 5 illustrates how intuition for technical contributions can be obtained via a few well-thought-out simulation studies.

Weaknesses: An inherent drawback of performing information-theoretic research is that a relatively high bar must be cleared in order to actually obtain the desired results. This issue manifested itself when 1) I made a technical error in the conference version of this paper and 2) I glossed over several critical details in the proofs of our results, which put a crimp in the review process. In retrospect, I should have obtained a more solid grasp of multiuser information theory before tackling this open problem. We were also unable to obtain a sharper outer bound, which limited our options for journal submission; for example, our paper would have been rejected by the IEEE Transactions on Information Theory.

This paper, in some sense, signaled my entry into the world of academia. On a side note, I would like to commend the JCN publication staff, as they did a superb job throughout the paper review and editing process. For interested researchers, the JCN does have the occasional compelling special issue; their guest editors also tend to be fairly well-known in their respective sub-fields.

Finding a Good Research Topic September 27, 2008

Posted by flashbuzzer in Research.
add a comment

I recently wrote this post on my research group’s blog. While it probably best applies to graduate students in wireless communications, some of the ideas expressed there should be useful for grad students in other disciplines.