| Mobile and cloud computing have been growing at a tremendous speed over the past decade, with companies around the world deploying massive data centers that serve billions of people. As we connect more devices to the Internet, and storing increasing amount of data, there is no doubt that we are becoming more likely to encounter errors with data. To protect data, one can use error correction codes. However, some latest technologies such as optical transport networks and flash memories have new requirements for error controls. To meet these requirements, our goal in this dissertation is to develop algorithms that are (i) efficient in terms of computational complexity and (ii) capable of correcting more errors than existing schemes.;In this dissertation, we apply the alternating direction method of multipliers (ADMM) to decoding error correction codes. In particular, we focus on the following codes: binary low-density parity-check (LDPC) codes, non-binary LDPC codes, and multipermutation codes. Although linear programming (LP) decoding algorithms have been proposed for all three codes, these LP decoding algorithms hardly meet our goals.;Regarding our first goal of reducing decoding complexity, we adopt the following two-step approach for all decoding problems in this dissertation. First, we decompose each decoding problem into subproblems using ADMM. Then, we solve the subproblems by studying the geometries involved in the decoding constraints. Regarding our second goal of improving error performance, we propose new decoding problems that can leverage the ADMM decoding framework. For LDPC codes, we improve LP decoding error performance by penalizing pseudocodewords, which are the non-integer vertices of the LP relaxation to which LP decoding fails. For multipermutation codes, we propose new soft decoding techniques, which can outperform hard decoding techniques based on quantized multipermutation rankings. |
