Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (8 results)

  • Article
  • Peer Reviewed
UC San Diego Previously Published Works (2012)
Two mappings in a finite field, the Frobenius mapping and the cyclic shift mapping, are applied on lines in PG($n,p$) or codes in the Grassmannian, to form automorphisms groups in the Grassmanian and in its codes. These automorphisms are examined on two classical coding problems in the Grassmannian. The first is the existence of a parallelism with lines in the related projective geometry and the second is the existence of a Steiner structure. A computer search was applied to find parallelisms and codes. A new parallelism of lines in PG(5,3) was formed. A parallelism with these parameters was not known before. A large code which is only slightly short of a Steiner structure was formed.
    Cover page: Automorphisms of Codes in the Grassmann Scheme
    • Thesis
    • Peer Reviewed
    UC San Diego Electronic Theses and Dissertations (2018)

    The discovery of channel polarization and polar codes is universally recognized as an historic breakthrough in coding theory. Polar codes provably achieve the capacity of any memoryless symmetric channel, with low encoding and decoding complexity. Moreover, for short block lengths, polar codes under specific decoding algorithms are currently the best known coding scheme for binary-input Gaussian channels. Due to this and other considerations, 3GPP has recently decided to incorporate polar codes in the 5G wireless communications standard. Soon enough, a remarkably short time after their invention, we will be all using polar codes whenever we make a phone call or access the Internet on a mobile device.

    Our goal in this dissertation is to explore new frontiers in polar coding, thereby fundamentally advancing the current state-of-the-art in the field. Parts of the results are immediately relevant for successful deployment of polar codes in wireless systems, whereas other parts will focus on key theoretical problems in polar coding that have a longer time-horizon.

    We begin by studying the effect of the polarization kernels in the asymptotic behavior of polar codes. We show that replacing the conventional 2×2 kernel in the construction of polar codes with that of a larger size can reduce the gap to the capacity if the larger kernel is carefully selected. A heuristic algorithm is proposed that helps to find such kernels. Furthermore, we prove that a near-optimal scaling behavior is achievable if one is allowed to increase the kernel size as needed. We also study the computational complexity of decoding algorithms for polar codes with large kernels, which are viewed as their main implementation obstacle.

    Moving on to the decoding algorithms, we carefully analyze the performance of the successive cancellation decoder with access to the abstract concept of Arikan’s genie. The CRC-aided successive-cancellation list decoding, the primary decoding method of polar codes, is commonly viewed as an implementation of the Arikan’s genie. However, it comes short at completely simulating the genie since the auxiliary information (CRC) comes to the help only at the end of the decoding process. We overcome this problem by introducing the convolutional decoding algorithm of polar codes that is based on a high-rate convolutional pre-coder and utilizes Viterbi Algorithm to mimic the genie all the way through the SC decoding process.

    Lastly, we look into channels with deletions. A key assumption in the traditional polar coding is to transmit coded symbols over independent instances of the communication channel. Channels with memory and in particular, deletion channels, do not follow this rule. We introduce a modified polar coding scheme for these channels that depend on much less computational power for decoding than the existing solutions. We also extend the polarization theorems to provide theoretical guarantee and to prove the correctness of our algorithms.

      Cover page: New Frontiers in Polar Coding: Large Kernels, Convolutional Decoding, and Deletion Channels
      • Article
      • Peer Reviewed
      UC San Diego Previously Published Works (2017)
        Cover page: Minimum Storage Regenerating Codes for All Parameters
        • Article
        • Peer Reviewed
        UC San Diego Previously Published Works (2020)
        A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a t-(n,k,λ) combinatorial design with tiny, yet positive, probability. The proof method of KLP is adapted to show the existence of large sets of designs and similar combinatorial structures as follows. We modify the random choice and the analysis to show that, under the same conditions, not only does a t-(n,k,λ) design exist but, in fact, with positive probability there exists a large set of such designs — that is, a partition of the set of k-subsets of [n] into t-(n,k,λ) designs. Specifically, using the probabilistic approach derived herein, we prove that for all sufficiently large n, large sets of t-(n,k,λ) designs exist whenever k>12t and the necessary divisibility conditions are satisfied. This resolves the existence conjecture for large sets of designs for all k>12t.
          Cover page: Probabilistic existence of large sets of designs
          • Article
          • Peer Reviewed
          UC San Diego Previously Published Works (2014)
          A t-( n, k, λ) design over Fq is a collection of k-dimensional subspaces of Fqn, called blocks, such that each t-dimensional subspace of Fqn is contained in exactly λ blocks. Such t-designs over Fq are the q-analogs of conventional combinatorial designs. Nontrivial t-( n, k, λ) designs over Fq are currently known to exist only for t ≤ 3. Herein, we prove that simple (meaning, without repeated blocks) nontrivial t-( n, k, λ) designs over Fq exist for all t and q, provided that k > 12( t + 1) and n is sufficiently large. This may be regarded as a q-analog of the celebrated Teirlinck theorem for combinatorial designs. © 2014 Elsevier Inc.
            Cover page: Nontrivial t-designs over finite fields exist for all t
            • Article
            • Peer Reviewed
            UC San Diego Previously Published Works (2017)
              Cover page: Polar Coding for the Binary Erasure Channel With Deletions
              • Article
              • Peer Reviewed
              UC San Diego Previously Published Works (2016)
              In this work, we present hardware and software implementations of flexible polar systematic encoders and decoders. The proposed implementations operate on polar codes of any length less than a maximum and of any rate. We describe the low-complexity, highly parallel, and flexible systematic-encoding algorithm that we use and prove its correctness. Our hardware implementation results show that the overhead of adding code rate and length flexibility is little, and the impact on operation latency minor compared to code-specific versions. Finally, the flexible software encoder and decoder implementations are also shown to be able to maintain high throughput and low latency.
                Cover page: Flexible and Low-Complexity Encoding and Decoding of Systematic Polar Codes
                • Article
                • Peer Reviewed
                UC San Diego Previously Published Works (2016)
                Let $\mathbb{F}_{q}^{n}$ be a vector space of dimension $n$ over the finite field $\mathbb{F}_{q}$. A $q$-analog of a Steiner system (also known as a $q$-Steiner system), denoted ${\mathcal{S}}_{q}(t,\!k,\!n)$, is a set ${\mathcal{S}}$ of $k$-dimensional subspaces of $\mathbb{F}_{q}^{n}$ such that each $t$-dimensional subspace of $\mathbb{F}_{q}^{n}$ is contained in exactly one element of ${\mathcal{S}}$. Presently, $q$-Steiner systems are known only for $t\,=\,1\!$, and in the trivial cases $t\,=\,k$ and $k\,=\,n$. In this paper, the first nontrivial $q$-Steiner systems with $t\,\geqslant \,2$ are constructed. Specifically, several nonisomorphic $q$-Steiner systems ${\mathcal{S}}_{2}(2,3,13)$ are found by requiring that their automorphism groups contain the normalizer of a Singer subgroup of $\text{GL}(13,2)$. This approach leads to an instance of the exact cover problem, which turns out to have many solutions.
                  Cover page: EXISTENCE OF -ANALOGS OF STEINER SYSTEMS
                  Top