Quadratic Permutation Polynomial

Description

The Quadratic Permutation Polynomial (QPP) is a core component of the turbo code interleaver design specified in 3GPP standards, primarily for LTE (E-UTRA) and NR. It is defined by a simple quadratic function of the form π(x) = (f1 * x + f2 * x²) mod K, where x is the input bit index (0 ≤ x < K), K is the interleaver block size, and f1 and f2 are integer coefficients standardized for different values of K. This function generates a deterministic, one-to-one permutation that maps each input bit position to a unique output position. The interleaver's operation is integral to the turbo coding process, where it is applied to separate the two constituent encoders, ensuring that the parity bits generated are based on different orderings of the input systematic bits.

Architecturally, the QPP interleaver is implemented within the channel coding subsystem of the physical layer. When a transport block is prepared for transmission, it is first segmented into code blocks if necessary, each sized to a supported K value. For each code block, the QPP function computes the interleaved address sequence. This sequence is used to reorder the input bits before they enter the second constituent encoder of the turbo encoder. The key property of the QPP is that it generates a contention-free interleaver, meaning multiple parallel processors can access the interleaver memory simultaneously without collisions, which is essential for high-throughput, low-latency hardware implementations.

Its role in the network is to enhance the performance of the forward error correction (FEC) scheme. By scattering burst errors—common in fading wireless channels—into random-like errors, the QPP interleaver enables the turbo decoder's iterative process to correct them more effectively. The algebraic structure of the QPP allows for efficient computation of the interleaving pattern without requiring large lookup tables, simplifying both the encoder and decoder design. This mathematical elegance, combined with proven performance gains in terms of bit error rate (BER) and block error rate (BLER), has made it a lasting choice from LTE Release 8 through to 5G NR.

Purpose & Motivation

The QPP was introduced to address specific limitations in the interleavers used in earlier 3GPP standards like UMTS. Prior turbo code interleavers, such as those in WCDMA, were based on algorithmic rules or table-based permutations that could be complex to implement and did not guarantee contention-free properties. As data rates and throughput demands increased with LTE, there was a need for an interleaving scheme that could support highly parallel decoder architectures (using multiple MAP decoders) to meet latency and throughput targets. The contention-free property is critical for parallelism because it prevents memory access conflicts when multiple processors read/write interleaved data simultaneously.

Historically, the search for a good interleaver involved balancing performance (distance spectrum properties) with implementation feasibility. The QPP solution emerged from academic research showing that quadratic polynomials could generate permutations with excellent spreading properties and inherent contention-free characteristics for a range of parallelization factors. 3GPP adopted QPP interleavers in LTE Release 8 to standardize a high-performance, yet implementable, interleaver that would future-proof the standard for evolving hardware capabilities. It solved the problem of enabling efficient, parallel turbo decoder implementations while maintaining the superior error correction performance needed for high-speed mobile broadband, a foundation that continues into 5G NR.

Key Features

• Contention-free interleaving enabling parallel decoder architectures
• Defined by a simple quadratic polynomial π(x) = (f1*x + f2*x²) mod K
• Standardized coefficients (f1, f2) for multiple block sizes (K)
• Algebraic structure allows computation without large lookup tables
• Provides excellent error scattering to improve turbo code performance
• Supports high-throughput, low-latency channel coding implementations

Evolution Across Releases

Defining Specifications