1.

Introduction

While the resolution of the sensors in the remote sensing space missions tends to increase, the bandwidth of the communication channel remains comparatively stable. As a consequence, the reduction of the captured data volume on-board satellites by means of compression is becoming ever more important, and becomes almost imperative for multispectral and hyperspectral sensors, since the amount of data captured is substantial.

When selecting or designing an algorithm for on-board data compression, we have to consider both, its coding efficiency and if the algorithm is suitable to be efficiently executed on the hardware that is available on a satellite. Among the possible hardware technologies that can be used for on-board data compression, field-programmable gate arrays (FPGAs) stand out, yielding a good compromise between performance and cost, as they present multiple advantages, such as the ability to apply parallel processing to increase throughput, provide flexibility, scalability, and data integrity features. However, space-qualified FPGAs, which are tolerant to solar radiation, are more difficult to manufacture, increasing their cost and reducing their performance. As a consequence, the requirement of low complexity for an on-board compression algorithm becomes even more important.

The Consultative Committee for Space Data Systems (CCSDS) offers currently a solution for lossless multispectral and hyperspectral image compression (CCSDS 123).¹ This solution has been proven to take a reduced amount of hardware resources,² fitting in a small space-qualified FPGA.³ Nevertheless, although lossless compression has been traditionally preferred to preserve all the information in the image, the current bandwidth and on-board storage restrictions make it necessary in some scenarios to resort to lossy compression in order to reduce the data volume appropriately. As a consequence, the CCSDS is currently working toward the definition of a lossy standard as an extension of the existing CCSDS 122 standard for image compression.⁴ The latter defines a two-dimensional (2-D) image coder that combines a wavelet transform with a bitplane encoder and that, if coupled with a spectral transform, would take advantage of the spectral correlation present in multispectral and hyperpectral data.

Transform-based methods for compression are known to be well-suited for lossy compression. However, they are also known to be usually computationally complex in terms of the number of operations and memory requirements. In particular, in Ref. 5, several three-dimensional (3-D) transform coding techniques for lossy hyperspectral image compression are compared, showing increased rate-distortion performance when a spectral Kahrunen–Loève transform (KLT) is employed, especially in the low bit-rate region. However, the KLT presents important disadvantages when its implementation on hardware is considered: it has a high computational cost and has high memory requirements. All these factors lead to a higher implementation difficulty, and often become insuperable obstacles when considering an implementation on space-qualified FPGAs.

A divide and conquer strategy was proposed in Ref. 6, in which the pairwise orthogonal transform (POT) is presented. The POT is a simple adaptive transform that only requires a small amount of side information, which, in turn allows a line-based application of the transform not previously available to other divide-and-conquer approaches (or the KLT). In most cases, it has a better coding performance than wavelet transforms and, at the same time, it overcomes the inconveniences of the KLT, achieving a notably lower computational cost and better component scalability, with very low memory requirements (a few orders of magnitude less than a full KLT). The POT has a better performance than the wavelets, although it does not reach the coding performance of a full KLT.

This work aims at validating that the low complexity of the POT makes it suitable for a space-qualified FPGA implementation. A register transfer level (RTL) description of the main arithmetic stages of the POT, namely the mean subtraction, the training of balanced and unbalanced pairwise operations, and the lifting network are provided and optimized in order to of achieve a low occupancy of the hardware resources, making it possible to synthesize the design on a space-qualified RTAX2000S or on an RTAX2000S-DSP, which contains additional dedicated digital signal processor (DSP) blocks. In order to limit the dynamic range expansion of the transform, the variant of the POT introduced in Ref. 7 is the one being implemented.

Despite the POT being significantly less demanding in terms of hardware resources than the KLT, in this paper we make it even more amenable for an implementation on a space-qualified FPGA. In particular, a description of the mathematical operations in the transform is provided, in such a way that they can be solved with integer arithmetic, making the transform fully reversible and bit-exact (i.e., output values are unambiguous down to the bit level), which enables progressive lossy-to-lossless and makes implementations much easier to validate. Moreover, the most computationally demanding operations of the transform are solved by means of lookup tables (LUTs).

We note that, despite the POT being proposed to be included by the CCSDS in the upcoming standard for lossy multispectral and hyperspectral compression, the final standard may be different from the description of the operations in the POT presented in this paper. Moreover, the POT is only a part of the whole compression engine, which is being designed such that existing implementations of CCSDS-122.0, such as the ASICs described in Refs. 8 and 9, can be leveraged to create a complete compression engine.

This paper is structured as follows: Section 2 provides an overview of the arithmetic elements in the POT in a bit-accurate way, the subsequent Sec. 3 reports the hardware design considerations, explaining the methodology followed to create an RTL description of the latter operations, Sec. 4 shows the implementation results and finally, Sec. 5 presents the conclusions.

2.

The Pairwise Orthogonal Transform: A Bit-Exact Definition

The POT is an approximation of the KLT at a fraction of its computational cost. It is a composition of three kinds of operations that, when combined into a multilevel structure, are employed to obtain the transformed image. Namely, these operations are the mean-subtraction operation, the balanced pairwise operation, and the unbalanced pairwise operation. For conciseness, this paper does not include a detailed description of the POT or the implemented variant; descriptions which are already available in Refs. 6 and 7.

In the following subsections we present a definition of the arithmetic operations of the transform, which makes it amenable for an implementation on the hardware available on a satellite. Specifically, the operations are described in a bit-exact way, utilizing only integer arithmetic. This will facilitate significantly the subsequent physical implementation of the POT. In this paper, the implementation target is an FPGA of the Microsemi RTAX family, which is currently space-qualified and is flown in current space missions. Reducing the complexity of the arithmetic operations becomes even more important due to the limited computational power of these devices, when compared with other nonqualified FPGA models that can be found nowadays in the market.

2.1.

Mean-Subtraction Operation

The mean-subtraction operation maps an input sequence of integer values $\{x_0,x_1,\dots ,x_{N-1}\}$ of size $N\ge 1$ to an output sequence $\{y_0,y_1,\dots ,y_{N-1}\}$, modifying the original values such that the output sequence has an arithmetic mean of approximately zero; see Fig. 1.

Fig. 1

Mean-subtraction operation.

For a given input sequence, the value $m$ is an approximation of the arithmetic mean of $x_i$, obtained as

Eq. (1)

$$m=\lfloor \frac{1}{N}\sum _{i=0}^{N-1}{x}_i\rfloor .$$

Given $m$, the result of the mean-subtraction operation is $y_i=x_i-m$ for $i=0,\dots ,N-1$.

2.2.

Pairwise Operation

The pairwise operation is defined in such a way that the output of the operation produces sequences that share virtually no correlation among each other.

Let $\{x_0,x_1,\dots ,x_{N-1}\}$ and $\{y_0,y_1,\dots ,y_{N-1}\}$ be two one-dimensional input sequences consisting of $N$ integer samples each, and with an arithmetic mean of approximately zero. Given these sequences, the pairwise operation produces two output sequences, $\{{\chi }_0,{\chi }_1,\dots ,{\chi }_{N-1}\}$ and $\{{\varphi }_0,{\varphi }_1,\dots ,{\varphi }_{N-1}\}$, consisting of $N$ samples each, and with an arithmetic mean also of approximately zero, as shown in Fig. 2

Fig. 2

The pairwise operation.

The pairwise operation changes in function of its current inputs. Two training parameters $B$ and $C$ are first derived from the inputs and then used to specialize the operation. These parameters are required to invert the operation and are stored as side information.

Additionally, the pairwise operation has a Boolean input, named flip, which changes the sign of all the elements of both output sequences.

The integer constant $\mathrm{\Omega }$ indicates the precision of pairwise operations. It must be set within the interval [9, 16] and it is constant for the whole compression process of an input image. This constant can be used to regulate the complexity of the implementation at the expense of minor coding performance penalties.

As a prerequisite to calculate the training parameters, $B$ and $C$ the scaled-up variances and covariance of $x_i$ and $y_i$ should be calculated as follows:

Eq. (2)

$$\widetilde{{\sigma }_x^2}=\sum _{i=0}^{N-1}{x}_i^2-N·{\lfloor \sum _{i=0}^{N-1}{x}_i\rfloor }^2,$$

Eq. (3)

$$\widetilde{{\sigma }_y^2}=\sum _{i=0}^{N-1}{y}_i^2-N·{\lfloor \frac{1}{N}\sum _{i=0}^{N-1}{y}_i\rfloor }^2,$$

Eq. (4)

$$\widetilde{{\sigma }_{x,y}}=\sum _{i=0}^{N-1}(x_i·y_i)-N·\lfloor \frac{1}{N}\sum _{i=0}^{N-1}{x}_i\rfloor ·\lfloor \frac{1}{N}\sum _{i=0}^{N-1}{y}_i\rfloor .$$

The training parameters $B$ and $C$ are then calculated as follows. When $\widetilde{{\sigma }_{x,y}}\ne 0$,

Eq. (5)

$$B=\frac{\widetilde{{\sigma }_{x,y}}}{|\widetilde{{\sigma }_{x,y}}|}\mathrm{and}C=\min \left(\max \right(\lfloor 2^{\mathrm{\Omega }-4}·\frac{\widetilde{{\sigma }_x^2}-\widetilde{{\sigma }_y^2}}{2·|\widetilde{{\sigma }_{x,y}}|}\rfloor ,-2^{\mathrm{\Omega }-2}),2^{\mathrm{\Omega }-2}-1).$$

Otherwise, when $\widetilde{{\sigma }_{x,y}}=0$,

Eq. (6)

$$B=-1\mathrm{and}C=\{\begin{array}{ll}{2}^{\mathrm{\Omega }-2}-1& \mathrm{if}\widetilde{{\sigma }_x^2}\ge \widetilde{{\sigma }_y^2},\\ -2^{\mathrm{\Omega }-2}& \text{otherwise}\end{array}.$$

After obtaining $B$ and $C$, the decorrelated output sequences can be obtained through a lifting network. The lifting network, requires computing the weights ${\tilde{w}}_1$, ${\tilde{w}}_2$, and ${\tilde{w}}_3$, and two flags: one to indicate whether the result shall be sign-changed (flag $s$) and the another to signal whether the outputs ${\chi }_i$ and ${\varphi }_i$ shall be permuted. Hence, the result of the pairwise operation (the values ${\chi }_i$ and ${\varphi }_i$) is produced by the lifting network shown in Fig. 3, where the values $x_i$ and $y_i$ are affected by three lifting steps (with weights ${\tilde{w}}_1$, ${\tilde{w}}_2$, and ${\tilde{w}}_3$), and the result is conditionally sign-changed and conditionally permuted.

Fig. 3

Lifting network of the pairwise operation.

Weights ${\tilde{w}}_1$, ${\tilde{w}}_2$, and ${\tilde{w}}_3$ are obtained from $B$ and $C$ as follows. Let

Eq. (7)

$$\tilde{t}=\{\begin{array}{ll}0& \mathrm{if}C=2^{\mathrm{\Omega }-2}-1\\ B·2^{\mathrm{\Omega }-1}& \mathrm{if}C=-2^{\mathrm{\Omega }-2}\\ B·\lfloor \sqrt{2^{2\mathrm{\Omega }-3}-\lfloor \frac{2^{2\mathrm{\Omega }+1}·C}{\lfloor \sqrt{2^8·C^2+2^{2\mathrm{\Omega }}}+0.5\rfloor }+0.5\rfloor }+0.5\rfloor & \text{otherwise}\end{array},$$

Eq. (8)

$$\tilde{p}=\lfloor (2^{\mathrm{\Omega }+1})\sqrt{1-{\left(\frac{\tilde{t}}{2^{\mathrm{\Omega }-1}}\right)}^2}+0.5\rfloor ,$$

and

Eq. (9)

$$\tilde{\sqrt{2}}=\lfloor (2^{\mathrm{\Omega }+2})\sqrt{2}+0.5\rfloor .$$

If $C<0$, then

Eq. (10)

$${\tilde{w}}_1=\lfloor (2^{\mathrm{\Omega }-4})\frac{2\tilde{p}-\tilde{\sqrt{2}}}{\tilde{t}}+0.5\rfloor ,{\tilde{w}}_2=\lfloor \frac{\tilde{\sqrt{2}}·\tilde{t}}{2^{\mathrm{\Omega }+3}}+0.5\rfloor ,{\tilde{w}}_3=\lfloor (2^{\mathrm{\Omega }-4})\frac{4\tilde{p}-\tilde{\sqrt{2}}}{\tilde{t}}+0.5\rfloor ,$$

and the output shall not be permuted; otherwise, when $C\ge 0$,

Eq. (11)

$${\tilde{w}}_1=\lfloor (2^{\mathrm{\Omega }-3})\frac{\tilde{\sqrt{2}}-16\tilde{t}}{\tilde{p}}+0.5\rfloor ,{\tilde{w}}_2=\lfloor -\frac{\tilde{\sqrt{2}}·\tilde{p}}{2^{\mathrm{\Omega }+4}}+0.5\rfloor ,{\tilde{w}}_3=\lfloor (2^{\mathrm{\Omega }-3})\frac{\tilde{\sqrt{2}}-8\tilde{t}}{\tilde{p}}+0.5\rfloor ,$$

and the output shall be permuted. The sign change is determined by

Eq. (12)

$$s=\{\begin{array}{ll}1& \mathrm{if}(C\ge 0\hspace{0.17em}\mathrm{or}\hspace{0.17em}B\ge 0)\text{and flip is false}\\ -1& \mathrm{if}(C\ge 0\hspace{0.17em}\mathrm{or}\hspace{0.17em}B\ge 0)\text{and flip is true}\\ -1& \mathrm{if}C<0\mathrm{and}B<0\text{and flip is false}\\ 1& \mathrm{if}C<0\mathrm{and}B<0\text{and flip is true}\end{array}.$$

Output values ${\chi }_i$ shall be sign-changed when $s$ is $-1$. Output values ${\varphi }_i$ shall be sign-changed when $C<0$ and $s$ is $-1$, or when $C\ge 0$ and $s$ is 1.

3.

Hardware Implementation of the Arithmetic Elements of the Pairwise Orthogonal Transform

We present in the following sections the implementation of the operations in the POT in order to estimate its complexity in terms of utilization of hardware resources and assess the feasibility for an implementation on a space-qualified FPGA. More specifically, the following operations are described at RTL: mean-subtraction; computation of the variance and covariance; computation of the training parameters, $B$ and $C$; the computation of the weights; and the lifting network. A flowchart showing the relationship between the aforementioned operations in the POT is displayed in Fig. 5.

Fig. 4

The unbalanced pairwise operation.

Fig. 5

Flowchart of the different operations in the pairwise orthogonal transform (POT), which are implemented in a field-programmable gate array.

3.1.

Main Design Considerations

The main objective of the presented hardware implementation is to optimize the amount of FPGA resources taken by the design; hence, we focus on reducing as much as possible the complexity of the operations, scheduling them sequentially when possible. For instance, the integer division operations which are needed to compute the mean values and to obtain the training parameter $C$ are solved by means of serial divisors in order to reduce the amount of hardware resources.

It is decided to split the design in several modules, which are described in VHDL. We designed a module that implements the mean subtraction, variance and covariance calculation, and the necessary operations to obtain the training parameters $B$ and $C$, as it was described in Sec. 2. Once $B$ and $C$ are available, it is necessary to calculate the weights. From the equations presented in Sec. 2, we can infer that these operations are rather complex and might become computationally expensive for an FPGA. We have observed, however, that it is possible reduce the complexity and computational load of the overall design by utilizing a LUT that, given the parameters $B$, $C$, flip, and a flag that indicates is the transform is balanced or unbalanced, will produce the desired weights (${\tilde{w}}_1$, ${\tilde{w}}_2$, and ${\tilde{w}}_3$); the sign change; and the flag indicating that the output shall be permuted. Finally, a module which implements the lifting network is also described in VHDL. The basic block diagram of the design is shown in Fig. 6.

Fig. 6

Block diagram of the implemented elements of the POT: mean-subtraction, computation of training parameters, production of the weights with a lookup table, and lifting network.

In order to find out which is the best implementation solution for the LUT, from which the weights are obtained, we perform an estimation of the amount of resources needed to implement it only with combinatorial logic. The results are presented in Table 1, where it can be observed that the number of combinatorial cells needed to implement such LUT is highly dependant on $\mathrm{\Omega }$. Given that the combinatorial cells required for such LUT rise considerably as $\mathrm{\Omega }$ grows—with, for example, a 14% of the RTAX2000S resources employed for $\mathrm{\Omega }=11$—an alternative solution is proposed in order to reduce the area occupancy, which is to store the necessary LUT values in the internal RAM of the FPGA. The values can be stored in an external electrically erasable/programmable read-only memory (EEPROM), that would be loaded to RAM upon system start-up.

Table 1

Combinatorial cells needed to implement the LUTs.

Ω	Combinatorial cells
9	917
10	1685
11	3010
12	5446

4.

Implementation Results

The synthesis of the previously described module has been performed on an RTAX2000S and an RTAX2000S-DSP, which are manufactured by Microsemi and are space-qualified. The main difference between them is that the RTAX2000S-DSP contains dedicated DSP blocks. Several different configurations of the top module are synthesized, varying the parameter that indicates if the number of input samples is a power-of-two (P2), varying the number of input samples ($N$), or varying the number of bits per pixel (bpp). In all cases $\mathrm{\Omega }$ is set to 16. The different combinations of parameters can be observed in Fig. 8. We note that, even when $N$ is a power-of-two, if we do not inform explicitly the core with the corresponding parameter, the value will be interpreted as a nonpower-of-two value, i.e., the integer divisors will be used, they will not be replaced with bit shifts. This is the case of configurations C5 to C8.

Fig. 7

Architecture of the mean-subtraction, balanced, and unbalanced operations.

Fig. 8

Structure for parameter setting and resulting configurations.

Table 2 shows the hardware occupancy and maximum frequency of the implemented module obtained for the different configurations in both target FPGAs. The occupancy results are presented in terms of the percentage of combinatorial cells, sequential cells, and blocks of RAM (BRAM) utilized. For RTAX2000S-DSP device the percentage of used DSP blocks is also displayed.

Table 2

Synthesis results on a RTAX2000S and on an RTAX2000-DSP for different configurations.

In order to facilitate the comparison of the presented results, the occupancy values are also displayed in the graphs of Figs. 9 and 10. We can observe that the complete module implementing the POT can be synthesized on an RTAX2000S for any of the presented configurations. The most demanded resource are the combinatorial cells in the RTAX2000S and the internal BRAM in the RTAX2000S-DSP. Comparing both FPGA models, we can see that the number of combinatorial cells occupied is reduced for the RTAX2000S-DSP, which has taken advantage of the DSP blocks that it contains to perform specific computations that, otherwise, would be performed with combinatorial logic. We can also observe that the occupancy of resources is significantly higher when the input samples are represented with 16 bpp. However, there is not a significant increase in the number of resources utilized when we change the number of input samples from 256 to 512.

Fig. 9

Occupancy of the different configurations on an RTAX2000S.

Fig. 10

Occupancy of the different configurations on an RTAX2000S-DSP.

The frequency results can be observed and compared in Fig. 11. It can be seen that the frequency increases significantly with the RTAX2000S-DSP. The maximum and minimum frequencies for the RTAX2000S are 37.58 and 29.92 MHz, respectively. For the RTAX2000S-DSP the maximum frequency is 73.50 MHz and the minimum frequency is 53.83 MHz. The frequency values decrease as the bit-width of the input samples increases. No significant differences in the frequencies are found when the number of samples increases.

Fig. 11

Maximum frequency of the different configurations on an RTAX2000S and an RTAX2000S-DSP.

The intent of this paper is to show the feasibility of an FPGA implementation of the POT, and as such the implementation has not been optimized for throughput. Anyhow, a brief discussion follows to illustrate on which could be the throughput of the whole compression engine. The proposed implementation is able to produce a transformed sample every four clock cycles, which yields a minimum throughput of $12.5\mathrm{MSamples}/\mathrm{s}$ for configuration C1 and a maximum of $18.4\mathrm{MSamples}/\mathrm{s}$ for configuration C8.

To complete the whole 3-D compression engine, a 2-D compressor implementing the CCSDS-122.0, such as the CCSDS wavelet image compression (CWICOM) ASIC, is utilized after the POT. The CWICOM is able to operate at up to $60\mathrm{MSamples}/\mathrm{s}$.⁸ While the throughput of both elements is of similar magnitude, future optimizations of the POT implementation will be focused on improving its throughput, in such a way that it can yield one transformed sample per clock cycle.

5.

Conclusions

This paper examines the hardware complexity of the arithmetic elements of the POT, namely the mean-subtraction operation, the training of the transform, and the lifting network. A bit-exact description of the operations is provided and utilized to create a hardware implementation with reduced complexity that only utilizes integer arithmetic. A LUT is used to eliminate the most computationally demanding operations of the POT. We perform the synthesis of the described hardware on two space-qualified FPGA, namely the RTAX2000S, and the RTAX2000S-DSP with a different number of input samples represented with different bit depths. We observed that for any of the studied configurations, the complete design fits in the target FPGAs. The worst-case in terms of occupancy shows a 74% of combinatorial cell usage in the RTAX2000S. The best-case for the same FPGA has a maximum occupancy of 24.13% of the combinatorial cells. Furthermore, we observed that the RTAX2000S-DSP offers the possibility of reducing substantially the amount of combinatorial cells used, by utilizing dedicated DSP blocks. This FPGA also yields higher frequency values, displaying a maximum frequency of 73 MHz.

These results show that the POT, which is only a part of a whole compression engine for multispectral and hyperspectral images, presents a low hardware complexity, making it a good candidate for an on-board hardware implementation.