Image encoding/decoding method and device therefor

[0001] This application is a continuation of U.S. patent application Ser. No. 18/386,135 filed Nov. 1, 2023, now allowed, which is a continuation of Ser. No. 17/716,772 filed Apr. 8, 2022, now U.S. patent Ser. No. 11/863,778 issued Jan. 2, 2024, which is a continuation of Ser. No. 17/266,407 filed Feb. 5, 2021 now U.S. patent Ser. No. 11/412,242 issued Aug. 9, 2022 a National Stage Application of International Application No. PCT/KR2019/009990, filed on Aug. 8, 2019, which claims priority under 35 U.S.C. 119(e) to a U.S. Provisional Application No. 62/716,355 filed on Aug. 8, 2018, which is hereby incorporated by reference herein in their entirety.

[0002] The present disclosure relates to a method and apparatus for encoding/decoding a video and, more particularly, to a technology for performing a transform/inverse transform based on a Multiple Transform Selection (MTS).

[0003] Next-generation video content will have characteristics of a high spatial resolution, a high frame rate, and high dimensionality of scene representation. In order to process such content, technologies, such as memory storage, a memory access rate, and processing power, will be remarkably increased.

[0004] Accordingly, it is necessary to design a new coding tool for more efficiently processing next-generation video content. Particularly, it is necessary to design a more efficient transform in terms of coding efficiency and complexity when a transform is applied.

[0005] The present disclosure is intended to propose an operation algorithm having low complexity for a transform kernel for video compression.

[0006] The present disclosure is intended to propose a method of designing discrete sine transform-7 (DST7) having low complexity.

[0007] The present disclosure is intended to propose a method of designing forward DST7 and inverse DST7 as a discrete Fourier transform (DFT).

[0008] The present disclosure is intended to propose a method of implementing DST7 through a one-dimensional DFT or a two-dimensional DFT.

[0009] The present disclosure is intended to propose a method of implementing DST7 using only an integer operation by applying various scaling methods.

[0010] The present disclosure is intended to propose a method of designing DST7 having a length 8, 16, or 32, through a method of implementing DST7 using a DFT and a method of implementing DST7 using only an integer operation.

[0011] The present disclosure is intended to propose an encoder/decoder structure for incorporating a new transform design.

[0012] The present disclosure is intended to propose an overall transform process according to an embodiment proposed in the present disclosure.

[0013] In an aspect of the present disclosure, a method of decoding a video signal based on a Multiple Transform Selection (MTS) may include parsing a first syntax element indicating whether the MTS is applied to an inverse transform of a current block, wherein the MTS indicates a transform mode using another transform type other than a predefined default transform type in the current block, deriving an inverse quantized transform coefficient array with the width and height of the current block by performing inverse quantization on the current block, determining a vertical transform type applied to a vertical direction and horizontal transform type applied to a horizontal direction of the current block based on the first syntax element, and deriving a residual sample array with the width and height of the current block by performing an inverse transform on the inverse quantized transform coefficient array using the vertical transform type and the horizontal transform type.

[0014] Preferably, the default transform type may be configured as DCT2, and the remaining transform types other than the default transform type may be configured as DST7 and DCT8.

[0015] Preferably, if the first syntax element indicates that the MTS is not applied to the inverse transform of the current block, the vertical transform type and the horizontal transform type may be determined as DCT2. If the first syntax element indicates that the MTS is applied to the inverse transform of the current block, each of the vertical transform type and the horizontal transform type may be determined as any one of DST7 and DCT8.

[0016] Preferably, the method further includes parsing a second syntax element indicating whether the MTS is available for an intra coding block and a third syntax element indicating whether the MTS is available for an inter coding block. When the second syntax element is 1, the first syntax element may be present in a transform unit syntax for the intra coding block, and when the third syntax element is 1, the first syntax element may be present in a transform unit syntax for the inter coding block.

[0017] Preferably, deriving the residual sample array may includes performing a one-dimensional transform process in the vertical direction on each of columns of the inverse quantized transform coefficient array using the vertical transform type, and performing, using the horizontal transform type, a one-dimensional transform process in the horizontal direction on each of rows of an intermediate sample array output by the one-dimensional transform process for each of the columns.

[0018] Preferably, performing the one-dimensional transform process in the horizontal direction may further include clipping an intermediate sample value output by the one-dimensional transform process for each of the columns based on a minimum value and maximum value of a predefined coefficient.

[0019] In another aspect of the present disclosure, an apparatus for decoding a video signal based on a Multiple Transform Selection (MTS) may include a syntax element parsing unit configured to parse a first syntax element indicating whether the MTS is applied to an inverse transform of a current block, wherein the MTS indicates a transform mode using another transform type other than a predefined default transform type in the current block, an inverse quantized transform coefficient derivation unit configured to derive an inverse quantized transform coefficient array with the width and height of the current block by performing inverse quantization on the current block, a transform type determination unit configured to determine a vertical transform type applied to a vertical direction and horizontal transform type applied to a horizontal direction of the current block based on the first syntax element, and a residual sample derivation unit configured to derive a residual sample array with the width and height of the current block by performing an inverse transform on the inverse quantized transform coefficient array using the vertical transform type and the horizontal transform type.

[0020] Preferably, the default transform type may be configured as DCT2, and the remaining transform types other than the default transform type may be configured as DST7 and DCT8.

[0021] Preferably, if the first syntax element indicates that the MTS is not applied to the inverse transform of the current block, the vertical transform type and the horizontal transform type may be determined as DCT2. If the first syntax element indicates that the MTS is applied to the inverse transform of the current block, each of the vertical transform type and the horizontal transform type may be determined as any one of DST7 and DCT8.

[0022] Preferably, the syntax element parsing unit may be configured to parse a second syntax element indicating whether the MTS is available for an intra coding block and a third syntax element indicating whether the MTS is available for an inter coding block. When the second syntax element is 1, the first syntax element may be present in a transform unit syntax for the intra coding block, and when the third syntax element is 1, the first syntax element may be present in a transform unit syntax for the inter coding block.

[0023] Preferably, the residual sample derivation unit may be configured to perform a one-dimensional transform process in the vertical direction on each of columns of the inverse quantized transform coefficient array using the vertical transform type and to perform, using the horizontal transform type, a one-dimensional transform process in the horizontal direction on each of rows of an intermediate sample array output by the one-dimensional transform process for each of the columns.

[0024] Preferably, the residual sample derivation unit may be configured to clip an intermediate sample value output by the one-dimensional transform process for each of the columns based on a minimum value and maximum value of a predefined coefficient.

[0025] The present disclosure can reduce a memory use and operation complexity by providing the method of designing discrete sine transform-7 (DST7) having low complexity.

[0026] Furthermore, the present disclosure can reduce the complexity of DST7 through an FFT algorithm by designing forward DST7 and inverse DST7 as DFTs when encoding a still image or a moving image.

[0027] As described above, operation complexity can be reduced and coding efficiency can be improved through the new operation algorithm having low complexity.

[0058] Hereinafter, a configuration and operation of an embodiment of the present disclosure will be described in detail with reference to the accompanying drawings, a configuration and operation of the present disclosure described with reference to the drawings are described as an embodiment, and the scope, a core configuration, and operation of the present disclosure are not limited thereto.

[0059] Further, terms used in the present disclosure are selected from currently widely used general terms, but in a specific case, randomly selected terms by an applicant are used. In such a case, in a detailed description of a corresponding portion, because a meaning thereof is clearly described, the terms should not be simply construed with only a name of terms used in a description of the present disclosure and a meaning of the corresponding term should be comprehended and construed.

[0060] Further, when there is a general term selected for describing the disclosure or another term having a similar meaning, terms used in the present disclosure may be replaced for more appropriate interpretation. For example, in each coding process, a signal, data, a sample, a picture, a frame, and a block may be appropriately replaced and construed. Further, in each coding process, partitioning, decomposition, splitting, and division may be appropriately replaced and construed.

[0061] In the present disclosure, Multiple Transform Selection (MTS) may refer to a method for performing transform using at least two transform types. This may also be expressed as an Adaptive Multiple Transform (AMT) or Explicit Multiple Transform (EMT), and likewise, mts_idx may also be expressed as AMT_idx, EMT_idx, tu_mts_idx, AMT_TU_idx, EMT_TU_idx, transform index, or transform combination index and the present disclosure is not limited to the expressions.

[0062] FIG. 1 is a schematic block diagram of an encoder in which encoding of a video signal is performed as an embodiment to which the present disclosure is applied.

[0063] Referring to FIG. 1, the encoder 100 may be configured to include an image division unit 110, a transform unit 120, a quantization unit 130, a dequantization unit 140, an inverse transform unit 150, a filtering unit 160, a decoded picture buffer (DPB) 170, an inter-prediction unit 180, an intra-prediction unit 185, and an entropy encoding unit 190.

[0064] The image division unit 110 may divide an input image (or picture or frame) input into the encoder 100 into one or more processing units. For example, the processing unit may be a Coding Tree Unit (CTU), a Coding Unit (CU), a Prediction Unit (PU), or a Transform Unit (TU).

[0065] However, the terms are only used for the convenience of description of the present disclosure and the present disclosure is not limited to the definition of the terms. In addition, in the present disclosure, for the convenience of the description, the term coding unit is used as a unit used in encoding or decoding a video signal, but the present disclosure is not limited thereto and may be appropriately interpreted according to the present disclosure.

[0066] The encoder 100 subtracts a prediction signal (or a prediction block) output from the inter-prediction unit 180 or the intra-prediction unit 185 from the input image signal to generate a residual signal (or a residual block) and the generated residual signal is transmitted to the transform unit 120.

[0067] The transform unit 120 may generate a transform coefficient by applying a transform technique to the residual signal. A transform process may be applied to a quadtree structure square block and a block (square or rectangle) divided by a binary tree structure, a ternary tree structure, or an asymmetric tree structure.

[0068] The transform unit 120 may perform a transform based on a plurality of transforms (or transform combinations), and the transform scheme may be referred to as Multiple Transform Selection (MTS). The MTS may also be referred to as an Adaptive Multiple Transform (AMT) or an Enhanced Multiple Transform (EMT).

[0069] The MTS (or AMT or EMT) may refer to a transform scheme performed based on a transform (or transform combinations) adaptively selected from the plurality of transforms (or transform combinations).

[0070] The plurality of transforms (or transform combinations) may include transforms (or transform combinations) described with reference to FIG. 6 of the present disclosure. In the present disclosure, the transform or the transform type may be written like DCT-Type 2, DCT-II, DCT-2, DCT2, for example.

[0071] The transform unit 120 may perform the following embodiments.

[0072] The present disclosure provides a method of designing forward DST7 and inverse DST7 as discrete Fourier transforms (DFT).

[0073] The transform unit 120 may implement DST7 through a one-dimensional DFT or a two-dimensional DFT.

[0074] Furthermore, the transform unit 120 may implement DST7 using only an integer operation by applying various scaling methods.

[0075] Furthermore, the transform unit 120 may design DST7 having a length 8, 16, or 32 through a method of implementing DST7 using a DFT and a method of implementing DST7 using only an integer operation.

[0076] Detailed embodiments thereof will be described in more detail in the present disclosure.

[0077] The quantization unit 130 may quantize the transform coefficient and transmits the quantized transform coefficient to the entropy encoding unit 190 and the entropy encoding unit 190 may entropy-code a quantized signal and output the entropy-coded quantized signal as a bit stream.

[0078] Although the transform unit 120 and the quantization unit 130 are described as separate functional units, the present disclosure is not limited thereto and may be combined into one functional unit. The dequantization unit 140 and the inverse transform unit 150 may also be similarly combined into one functional unit.

[0079] A quantized signal output from the quantization unit 130 may be used for generating the prediction signal. For example, inverse quantization and inverse transform are applied to the quantized signal through the dequantization unit 140 and the inverse transform unit 1850 in a loop to reconstruct the residual signal. The reconstructed residual signal is added to the prediction signal output from the inter-prediction unit 180 or the intra-prediction unit 185 to generate a reconstructed signal.

[0080] Meanwhile, deterioration in which a block boundary is shown may occur due to a quantization error which occurs during such a compression process. Such a phenomenon is referred to as blocking artifacts and this is one of key elements for evaluating an image quality. A filtering process may be performed in order to reduce the deterioration. Blocking deterioration is removed and an error for the current picture is reduced through the filtering process to enhance the image quality.

[0081] The filtering unit 160 applies filtering to the reconstructed signal and outputs the applied reconstructed signal to a reproduction device or transmits the output reconstructed signal to the decoded picture buffer 170. The inter-prediction unit 170 may use the filtered signal transmitted to the decoded picture buffer 180 as the reference picture. As such, the filtered picture is used as the reference picture in the inter prediction mode to enhance the image quality and the encoding efficiency.

[0082] The decoded picture buffer 170 may store the filtered picture in order to use the filtered picture as the reference picture in the inter-prediction unit 180.

[0083] The inter-prediction unit 180 performs a temporal prediction and/or spatial prediction in order to remove temporal redundancy and/or spatial redundancy by referring to the reconstructed picture. In this case, since the reference picture used for prediction is a transformed signal that is quantized and inverse quantized in units of the block at the time of encoding/decoding in the previous time, blocking artifacts or ringing artifacts may exist.

[0084] Accordingly, the inter-prediction unit 180 may interpolate a signal between pixels in units of a sub-pixel by applying a low-pass filter in order to solve performance degradation due to discontinuity or quantization of such a signal. In this case, the sub-pixel means a virtual pixel generated by applying an interpolation filter and an integer pixel means an actual pixel which exists in the reconstructed picture. As an interpolation method, linear interpolation, bi-linear interpolation, wiener filter, and the like may be adopted.

[0085] An interpolation filter is applied to the reconstructed picture to enhance precision of prediction. For example, the inter-prediction unit 180 applies the interpolation filter to the integer pixel to generate an interpolated pixel and the prediction may be performed by using an interpolated block constituted by the interpolated pixels as the prediction block.

[0086] Meanwhile, the intra-prediction unit 185 may predict the current block by referring to samples in the vicinity of a block which is to be subjected to current encoding. The intra-prediction unit 185 may perform the following process in order to perform the intra prediction. First, a reference sample may be prepared, which is required for generating the prediction signal. In addition, the prediction signal may be generated by using the prepared reference sample. Thereafter, the prediction mode is encoded. In this case, the reference sample may be prepared through reference sample padding and/or reference sample filtering. Since the reference sample is subjected to prediction and reconstruction processes, a quantization error may exist. Accordingly, a reference sample filtering process may be performed with respect to each prediction mode used for the intra prediction in order to reduce such an error.

[0087] The prediction signal generated through the inter-prediction unit 180 or the intra-prediction unit 185 may be used for generating the reconstructed signal or used for generating the residual signal.

[0088] FIG. 2 is a schematic block diagram of a decoder in which decoding of a video signal is performed as an embodiment to which the present disclosure is applied.

[0089] Referring to FIG. 2, the decoder 200 may be configured to include a parsing unit (not illustrated), an entropy decoding unit 210, a dequantization unit 220, an inverse transform unit 230, a filtering unit 240, a decoded picture buffer (DPB) unit 250, an inter-prediction unit 260, and an intra-prediction unit 265.

[0090] In addition, a reconstructed video signal output through the decoder 200 may be reproduced through a reproduction device.

[0091] The decoder 200 may receive the signal output from the encoder 100 of FIG. 1 and the received signal may be entropy-decoded through the entropy decoding unit 210.

[0092] The dequantization unit 220 obtains the transform coefficient from an entropy-decoded signal by using quantization step size information.

[0093] The inverse transform unit 230 inversely transforms the transform coefficient to obtain the residual signal.

[0094] In this case, the present disclosure provides a method for configuring a transform combination for each transform configuration group divided by at least one of a prediction mode, a block size or a block shape and the inverse transform unit 230 may perform inverse transform based on the transform combination configured by the present disclosure. Further, the embodiments described in the present disclosure may be applied.

[0095] The inverse transform unit 230 may perform the following embodiments.

[0096] The present disclosure provides a method of designing forward DST7 and inverse DST7 as discrete Fourier transforms (DFT).

[0097] The inverse transform unit 230 may implement DST7 through a one-dimensional DFT or a two-dimensional DFT.

[0098] Furthermore, the inverse transform unit 230 may implement DST7 using only an integer operation by applying various scaling methods.

[0099] Furthermore, the inverse transform unit 230 may design DST7 having a length 8, 16, or 32 through a method of implementing DST7 using a DFT and a method of implementing DST7 using only an integer operation.

[0100] In an embodiment, the inverse transform unit 230 may derive a transform combination corresponding to a transform index, and may perform an inverse transform on a current block in a vertical or horizontal direction using DST7 or DCT8. In this case, the transform combination may be composed of a horizontal transform and a vertical transform, and the horizontal transform and the vertical transform may correspond to any one of the DST7 or the DCT8.

[0101] In an embodiment, when a 33-point discrete Fourier transform (DFT) is applied to the DST7, the step of dividing one row or one column of the DST7 into two partial vector signals; and the step of applying 11-point DFT type 1 or 11-point DFT type 2 to the two partial vector signals may be included.

[0102] In an embodiment, when one row or one column of the DST7 is represented as src[0 . . . 15], the two partial vector signals may be divided into src[0 . . . 4] and src[5 . . . 15].

[0103] In an embodiment, when a 65-point discrete Fourier transform (DFT) is applied to the DST7, the step of dividing one row or one column of the DST7 into three partial vector signals; and the step of applying 13-point DFT type 1 or 13-point DFT type 2 to the three partial vector signals may be included.

[0104] In an embodiment, when one row or one column of the DST7 is represented as src[0 . . . 31], the three partial vector signals may be divided into src[0 . . . 5], src[6 . . . 18] and src[19 . . . 31].

[0105] In an embodiment, among the three partial vector signals, the 13-point DFT type 1 may be applied to the src[0 . . . 5], and the 13-point DFT type 2 may be applied to the src[6 . . . 18] and src[19 . . . 31].

[0106] Meanwhile, the inverse transform unit 230 may perform an inverse primary transform on a transform coefficient block in a vertical direction using a vertical primary transform, and may perform an inverse primary transform on the transform coefficient block in a horizontal direction using a horizontal primary transform.

[0107] Furthermore, in the present embodiment, after a vertical transform, a horizontal transform is applied, but the present disclosure is not limited thereto. That is, after a horizontal transform is applied, a vertical transform may be applied.

[0108] In an embodiment, a combination of the horizontal transform and the vertical transform may include at least one of embodiments of FIG. 6.

[0109] Although the dequantization unit 220 and the inverse transform unit 230 are described as separate functional units, the present disclosure is not limited thereto and may be combined into one functional unit.

[0110] The obtained residual signal is added to the prediction signal output from the inter-prediction unit 260 or the intra-prediction unit 265 to generate the reconstructed signal.

[0111] The filtering unit 240 applies filtering to the reconstructed signal and outputs the applied reconstructed signal to a generation device or transmits the output reconstructed signal to the decoded picture buffer unit 250. The inter-prediction unit 250 may use the filtered signal transmitted to the decoded picture buffer unit 260 as the reference picture.

[0112] In the present disclosure, the embodiments described in the transform unit 120 and the respective functional units of the encoder 100 may be equally applied to the inverse transform unit 230 and the corresponding functional units of the decoder, respectively.

[0113] FIG. 3 illustrates embodiments to which the disclosure may be applied, FIG. 3a is a diagram for describing a block split structure based on a quadtree (hereinafter referred to as a “QT”), FIG. 3b is a diagram for describing a block split structure based on a binary tree (hereinafter referred to as a “BT”), FIG. 3c is a diagram for describing a block split structure based on a ternary tree (hereinafter referred to as a “TT”), and FIG. 3d is a diagram for describing a block split structure based on an asymmetric tree (hereinafter referred to as an “AT”).

[0114] In video coding, one block may be split based on a quadtree (QT). Furthermore, one subblock split by the QT may be further split recursively using the QT. A leaf block that is no longer QT split may be split using at least one method of a binary tree (BT), a ternary tree (TT) or an asymmetric tree (AT). The BT may have two types of splits of a horizontal BT (2N×N, 2N×N) and a vertical BT (N×2N, N×2N). The TT may have two types of splits of a horizontal TT (2N×1/2N, 2N×N, 2N×1/2N) and a vertical TT (1/2N×2N, N×2N, 1/2N×2N). The AT may have four types of splits of a horizontal-up AT (2N×1/2N, 2N×3/2N), a horizontal-down AT (2N×3/2N, 2N×1/2N), a vertical-left AT (1/2N×2N, 3/2N×2N), and a vertical-right AT (3/2N×2N, 1/2N×2N). Each BT, TT, or AT may be further split recursively using the BT, TT, or AT.

[0115] FIG. 3a shows an example of a QT split. A block A may be split into four subblocks A0, A1, A2, and A3 by a QT. The subblock A1 may be split into four subblocks B0, B1, B2, and B3 by a QT.

[0116] FIG. 3b shows an example of a BT split. A block B3 that is no longer split by a QT may be split into vertical BTs C0 and C1 or horizontal BTs D0 and D1. As in the block C0, each subblock may be further split recursively like the form of horizontal BTs E0 and E1 or vertical BTs F0 and F1.

[0117] FIG. 3c shows an example of a TT split. A block B3 that is no longer split by a QT may be split into vertical TTs C0, C1, and C2 or horizontal TTs D0, D1, and D2. As in the block C1, each subblock may be further split recursively like the form of horizontal TTs E0, E1, and E2 or vertical TTs F0, F1, and F2.

[0118] FIG. 3d shows an example of an AT split. A block B3 that is no longer split by a QT may be split into vertical ATs C0 and C1 or horizontal ATs D0 and D1. As in the block C1, each subblock may be further split recursively like the form of horizontal ATs E0 and E1 or vertical TTs F0 and F1.

[0119] Meanwhile, BT, TT, and AT splits may be split together. For example, a subblock split by a BT may be split by a TT or AT. Furthermore, a subblock split by a TT may be split by a BT or AT. A subblock split by an AT may be split by a BT or TT. For example, after a horizontal BT split, each subblock may be split into vertical BTs or after a vertical BT split, each subblock may be split into horizontal BTs. The two types of split methods are different in a split sequence, but have the same finally split shape.

[0120] Furthermore, if a block is split, the sequence that the block is searched may be defined in various ways. In general, the search is performed from left to right or from top to bottom. To search a block may mean a sequence for determining whether to split an additional block of each split subblock or may mean a coding sequence of each subblock if a block is no longer split or may mean a search sequence when information of another neighbor block is referred in a subblock.

[0121] FIGS. 4 and 5 are embodiments to which the disclosure is applied. FIG. 4 illustrates a schematic block diagram of a transform and quantization unit 120/130 and a dequantization and transform unit 140/150 within the encoder, and FIG. 5 illustrates a schematic block diagram of a dequantization and transform unit 220/230 within the decoder.

[0122] Referring to FIG. 4, the transform and quantization unit 120/130 may include a primary transform unit 121, a secondary transform unit 122 and the quantization unit 130. The dequantization and transform unit 140/150 may include the dequantization unit 140, an inverse secondary transform unit 151 and an inverse primary transform unit 152.

[0123] Referring to FIG. 5, the dequantization and transform unit 220/230 may include the dequantization unit 220, an inverse secondary transform unit 231 and an inverse primary transform unit 232.

[0124] In the disclosure, when a transform is performed, the transform may be performed through a plurality of steps. For example, as in FIG. 4, two steps of a primary transform and a secondary transform may be applied or more transform steps may be used according to an algorithm. In this case, the primary transform may be referred to as a core transform.

[0125] The primary transform unit 121 may apply a primary transform on a residual signal. In this case, the primary transform may be pre-defined in a table form in the encoder and/or the decoder.

[0126] A discrete cosine transform type 2 (hereinafter “DCT2”) may be applied to the primary transform.

[0127] Alternatively, a discrete sine transform-type 7 (hereinafter called “DST7”) may be applied to a specific case. For example, in the intra prediction mode, the DST7 may be applied to a 4×4 block.

[0128] Further, the primary transform may adopt combinations of various transforms DST 7, DCT 8, DST 1, and DCT 5 of the Multiple Transform Selection (MTS). For example, FIG. 6 may be adopted.

[0129] The secondary transform unit 122 may apply the secondary transform to a primary transformed signal and here, the secondary transform may be predefined in the table in the encoder and/or the decoder.

[0130] As an embodiment, the secondary transform may conditionally adopt a non-separable secondary transform (hereinafter, referred to as ‘NSST’). For example, the NSST may be applied only to the intra prediction block and may have a transform set applicable to each prediction mode group.

[0131] In this case, the prediction mode group may be configured based on symmetry with respect to a prediction direction. For example, since prediction mode 52 and prediction mode 16 are symmetrical based on prediction mode 34 (diagonal direction), the same transform set may be applied by forming one group. In this case, when the transform for prediction mode 52 is applied, input data is transposed and then applied because prediction mode 52 has the same transform set as prediction mode 16.

[0132] Meanwhile, since the symmetry for the direction does not exist in the case of a planar mode and a DC mode, each mode has a different transform set and the corresponding transform set may include two transforms. In respect to the remaining direction modes, each transform set may include three transforms.

[0133] As another embodiment, the secondary transform may adopt combinations of various transforms DST 7, DCT 8, DST 1, and DCT 5 of the Multiple Transform Selection (MTS). For example, FIG. 6 may be adopted.

[0134] In another embodiment, DST7 may be applied as a primary transform.

[0135] In another embodiment, DCT8 may be applied as a primary transform.

[0136] As another embodiment, the NSST may not be applied to the entire primary transformed block but may be applied only to a top-left 8×8 area. For example, when the block size is 8×8 or more, 8×8 NSST is applied and when the block size is less than 8×8, 4×4 NSST is applied and in this case, the block is divided into 4×4 blocks and then, the 4×4 NSST is applied to each of the divided blocks.

[0137] As another embodiment, even in the case of 4×N/N×4 (N>=16), the 4×4 NSST may be applied.

[0138] The NSST, 4×4 NSST and 8×8 NSST are more specifically described through FIGS. 12 to 15 and other embodiments within the disclosure.

[0139] The quantization unit 130 may perform quantization for the secondary transformed signal.

[0140] The dequantization and inverse transform units 140 and 150 perform the above-described process in reverse, and a redundant description thereof will be omitted.

[0141] FIG. 5 is a schematic block diagram of a dequantization unit 220 and an inverse transform unit 230 in a decoder.

[0142] Referring to FIG. 5 above, the dequantization and inverse transform units 220 and 230 may include a dequantization unit 220, an inverse secondary transform unit 231, and an inverse primary transform unit 232.

[0143] The dequantization unit 220 obtains the transform coefficient from an entropy-decoded signal by using quantization step size information.

[0144] The inverse secondary transform unit 231 performs an inverse secondary transform for the transform coefficients. In this case, the inverse secondary transform represents an inverse transform of the secondary transform described with reference to FIG. 4 above.

[0145] As another embodiment, the secondary transform may adopt combinations of various transforms DST 7, DCT 8, DST 1, and DCT 5 of the Multiple Transform Selection (MTS). For example, FIG. 6 may be adopted.

[0146] The inverse primary transform unit 232 performs an inverse primary transform for the inverse secondary transformed signal (or block) and obtains the residual signal. In this case, the inverse primary transform represents the inverse transform of the primary transform described with reference to FIG. 4 above.

[0147] As an embodiment, the primary transform may adopt combinations of various transforms DST 7, DCT 8, DST 1, and DCT 5 of the Multiple Transform Selection (MTS). For example, FIG. 6 may be adopted.

[0148] As an embodiment of the present disclosure, the DST 7 may be applied to the primary transform.

[0149] As an embodiment of the present disclosure, the DCT 8 may be applied to the primary transform.

[0150] The present disclosure may provide a method for configuring a transform combination for each transform configuration group divided by at least one of a prediction mode, a block size or a block shape and the inverse primary transform unit 232 may perform the inverse transform based on the transform combination configured by the present disclosure. Further, the embodiments described in the present disclosure may be applied.

[0151] FIG. 6 is a table showing a transform configuration group to which Multiple Transform Selection (MTS) is applied as an embodiment to which the present disclosure is applied.

Transform Configuration Group to which Multiple Transform Selection (MTS) is Applied

[0152] In the present disclosure, a j-th transform combination candidate for transform configuration group G_i is represented by a pair shown in Equation 1 below.

[0153] $\begin{array}{cc}\left(H\left(G_i,j\right),V\left(G_i,j\right)\right)& \left[\mathrm{Equation}l\right]\end{array}$

• • [0154] wherein H(G_i, j) indicates the horizontal transform for the j-th candidate, and V(G_i, j) indicates the vertical transform for the j-th candidate. For example, in FIG. 6, H(G₃, 2)=DST 7, V(G₃, 2)=DCT 8 may be represented. Depending on a context, a value assigned to H(G_i, j) or V(G_i, j) may be a nominal value to distinguish transformations, as in the example above or may be an index value indicating the transform or may be a 2 dimensional (D) matrix for the transform.

[0155] Further, in the present disclosure, a 2D matrix value for DCT and DST may be represented as shown in Equation 2 and 3 below.

[0156] $\begin{array}{cc}\mathrm{DCT}\mathrm{type}2:C_N^{\mathrm{II}},\mathrm{DCT}\mathrm{type}8:C_N^{\mathrm{VIII}}& \left[\mathrm{Equation}2\right]\end{array}$ $\begin{array}{cc}\mathrm{DCT}\mathrm{type}7:S_N^{\mathrm{VII}},\mathrm{DCT}\mathrm{type}4:S_N^{\mathrm{IV}}& \left[\mathrm{Equation}3\right]\end{array}$

• • [0157] wherein whether the transform is DST or DCT is represented by S or C, a type number is represented as a superposition in the form of a Roman number, and N of a lower subscript indicates that the transform is an N×N transform. Further, in the 2D matrix such as the

[0158] $C_N^{\mathrm{II}}$
and

[0159] $S_N^{\mathrm{IV}},$
it is assumed that column vectors form a transform basis.

[0160] Referring to FIG. 6, the transform configuration groups may be determined based on the prediction mode and the number of groups may be a total of six groups G0 to G5. In addition, G0 to G4 correspond to a case where intra prediction is applied, and G5 represents transform combinations (or transform sets and transform combination sets) applied to the residual block generated by the inter prediction.

[0161] One transform combination may include a horizontal transform (or row transform) applied to rows of a corresponding 2D block and a vertical transform (or column transform) applied to columns.

[0162] In this case, each of all of the transform configuration groups may have four transform combination candidates. The four transform combinations may be selected or determined through transform combination indexes of 0 to 3 and the transform combination index may be encoded and transmitted from the encoder to the decoder.

[0163] As an embodiment, the residual data (or residual signal) obtained through the intra prediction may have different statistical characteristics according to the intra prediction mode. Therefore, as illustrated in FIG. 6 above, transforms other than a general cosine transform (e.g., DCT2) may be applied to each intra prediction mode.

[0164] Referring to FIG. 6 above, a case of using 35 intra prediction modes and a case of using 67 intra prediction modes are illustrated. A plurality of transform combinations may be applied to each transform configuration group divided in each intra prediction mode column. For example, the plurality of transform combinations may include four (row direction transforms and column direction transforms) combinations. As a specific example, DST-7 and DST-5 may be applied in a row (horizontal) direction and a column (vertical) direction in group 0, and as a result, a total of four combinations are available.

[0165] Since a total of four transform kernel combinations may be applied to each intra prediction mode, a transform combination index for selecting one of the transform kernel combinations may be transmitted every transform unit. In the present disclosure, the transform combination index may be called MTS index and expressed as mts_idx.

[0166] Further, in addition to the transform kernels presented in FIG. 6 above, a case where DCT2 is optimal for both the row direction and the column direction due to characteristics of the residual signal may occur. Accordingly, the MTS flag is defined for each coding unit to adaptively perform the transform. In this case, when the MTS flag is 0, DCT2 may be applied to both the row direction and the column direction and when the MTS flag is 1, one of four combinations may be selected or determined through the MTS index.

[0167] As an embodiment, when the MTS flag is 1, if the number of non-zero transform coefficients for one transform unit is not greater than a threshold, the DST-7 may be applied to both the row direction and the column direction without applying the transform kernels of FIG. 6 above. For example, the threshold may be configured to 2, which may be configured differently based on the block size or the size of the transform unit. This is also applicable to other embodiments in the present disclosure.

[0168] As an embodiment, if the number of non-zero transform coefficients is not greater than the threshold by first parsing the transform coefficient values, an additional information transmission amount may be reduced by applying the DST-7 without parsing the MTS index.

[0169] As an embodiment, when the MTS flag is 1, if the number of non-zero transform coefficients is greater than the threshold for one transform unit, the MTS index may be parsed and the horizontal transform and the vertical transform may be determined based on the MTS index.

[0170] As an embodiment, the MTS may be applied only when both a width and a height of the transform unit are equal to or smaller than 32.

[0171] As an embodiment, FIG. 6 above may be preconfigured through off-line training.

[0172] As an embodiment, the MTS index may be defined as one index which may simultaneously indicate the horizontal transform and the vertical transform. Alternatively, the MTS index may separately define a horizontal transform index and a vertical transform index.

[0173] In an embodiment, the MTS flag or the MTS index may be defined in at least one level of a sequence, a picture, a slice, a block, a coding unit, a transform unit or a prediction unit. For example, the MTS flag or the MTS index may be defined in at least one level of a coding unit or a transform unit.

[0174] FIG. 7 is a flowchart showing an encoding process in which Multiple Transform Selection (MTS) is performed as an embodiment to which the present disclosure is applied.

[0175] In the present disclosure, an embodiment in which transforms are a separately applied to the horizontal direction and the vertical direction is basically described, but the transform combination may be constituted even by non-separable transforms.

[0176] Alternatively, the transform combination may be configured by a mixture of separable transforms and non-separable transforms. In this case, when the non-separable transform is used, row/column transform selection or horizontal/vertical direction selection may not be required and only when the separable transform is selected, the transform combinations of FIG. 6 above may be used.

[0177] Further, schemes proposed by the present disclosure may be applied regardless of the primary transform or the secondary transform. That is, there is no limit that the schemes should be applied only to any one of both the primary transform and the secondary transform and the schemes may be applied to both the primary transform and the secondary transform. In this case, the primary transform may mean a transform for transforming the residual block first and the secondary transform may mean a transform for applying the transform to the block generated as a result of the primary transform.

[0178] First, the encoder may determine the transform configuration group corresponding to the current block (S710). In this case, the transform configuration group may mean the transform configuration group of FIG. 6 above and the present disclosure is not limited thereto and the transform configuration group may include other transform combinations.

[0179] The encoder may perform a transform for candidate transform combinations available in the transform configuration group (S720).

[0180] As a result of performing the transform, the encoder may determine or select a transform combination having a smallest rate distortion (RD) cost (S730).

[0181] The encoder may encode the transform combination index corresponding to the selected transform combination (S740).

[0182] FIG. 8 is a flowchart showing a decoding process in which Multiple Transform Selection (MTS) is performed as an embodiment to which the present disclosure is applied.

[0183] First, the decoder may determine the transform configuration group for the current block (S810).

[0184] The decoder may parse (or obtain) the transform combination index from the video signal and here, the transform combination index may correspond to any one of the plurality of transform combinations in the transform configuration group (S820). For example, the transform configuration group may include Discrete Sine Transform type (DST) 7 and Discrete Cosine Transform type (DST) 8. The transform combination index may be referred to as the MTS index.

[0185] As an embodiment, the transform configuration group may be configured based on at least one of the prediction mode, the block size, or the block shape of the current block.

[0186] The decoder may derive the transform combination corresponding to the transform combination index (S830). In this case, the transform combination may include the horizontal transform and the vertical transform, and may include at least one of the DST-7 or the DCT-8.

[0187] Further, the transform combination may mean the transform combination described with reference to FIG. 6 above, but the present disclosure is not limited thereto. That is, the transform combination may be configured by other transform combinations depending on other embodiments in the present disclosure.

[0188] The decoder may perform the inverse transform for the current block based on the transform combination (S840). When the transform combination includes the row (horizontal) transform and the column (vertical) transform, the column (vertical) transform may be applied after applying the row (horizontal) transform first. However, the present disclosure is not limited thereto and the transform order may be reversed or when the transform combination includes the non-separable transforms, the non-separable transform may be immediately applied.

[0189] As an embodiment, when the vertical transform or the horizontal transform is the DST-7 or the DCT-8, the inverse transform of the DST-7 or the inverse transform of the DCT-8 may be applied to each column and then applied to each row.

[0190] As an embodiment, in respect to the vertical transform or the horizontal transform, different transform may be applied to each row and/or to each column.

[0191] As an embodiment, the transform combination index may be obtained based on the MTS flag indicating whether the MTS is performed. That is, the transform combination index may be obtained when the MTS is performed according to the MTS flag.

[0192] As an embodiment, the decoder may check whether the number of non-zero transform coefficients is greater than the threshold. In this case, the transform combination index may be obtained when the number of non-zero transform coefficients is greater than the threshold.

[0193] As an embodiment, the MTS flag or the MTS index may be defined in at least one level of a sequence, a picture, a slice, a block, a coding unit, a transform unit, or a prediction unit.

[0194] As an embodiment, the inverse transform may be applied only when both the width and the height of the transform unit are equal to or smaller than 32.

[0195] On the other hand, as another embodiment, a process of determining the transform configuration group and a process of parsing the transform combination index may be performed at the same time. Alternatively, step S810 above may be preconfigured and omitted in the encoder and/or the decoder.

[0196] FIG. 9 is a flowchart for describing a process of encoding an MTS flag and an MTS index as an embodiment to which the present disclosure is applied.

[0197] The encoder may determine whether the Multiple Transform Selection (MTS) is applied to the current block (S910).

[0198] When the Multiple Transform Selection (MTS) is applied, the encoder may encode MTS flag=1 (S920).

[0199] In addition, the encoder may determine the MTS index based on at least one of the prediction mode, the horizontal transform, and the vertical transform of the current block (S930). In this case, the MTS index may mean an index indicating any one of the plurality of transform combinations for each intra prediction mode and the MTS index may be transmitted for each transform unit.

[0200] When the MTS index is determined, the encoder may encode the MTS index (S940).

[0201] On the other hand, when the Multiple Transform Selection (MTS) is not applied, the encoder may encode MTS flag=0 (S950).

[0202] FIG. 10 is a flowchart for describing a decoding process in which a horizontal transform or vertical transform is applied to a row or a column based on an MTS flag and an MTS index as an embodiment to which the present disclosure is applied.

[0203] The decoder may parse the MTS flag from the bit stream (S1010). In this case, the MTS flag may indicate whether the Multiple Transform Selection (MTS) is applied to the current block.

[0204] The decoder may determine whether the Multiple Transform Selection (MTS) is applied to the current block based on the MTS flag (S1020). For example, it may be checked whether the MTS flag is 1.

[0205] When the MTS flag is 1, the decoder may check whether the number of non-zero transform coefficients is greater than (or equal to or greater than) the threshold (S1030). For example, the threshold may be configured to 2, which may be configured differently based on the block size or the size of the transform unit.

[0206] When the number of non-zero transform coefficients is greater than the threshold, the decoder may parse the MTS index (S1040). In this case, the MTS index may mean any one of the plurality of transform combinations for each intra prediction mode or inter prediction mode and the MTS index may be transmitted for each transform unit. Alternatively, the MTS index may mean an index indicating any one transform combination defined in a preconfigured transform combination table and here, the preconfigured transform combination table may mean FIG. 6 above, but the present disclosure is limited thereto.

[0207] The decoder may derive or determine the horizontal transform and the vertical transform based on at least one of the MTS index and the prediction mode (S1050).

[0208] Alternatively, the decoder may derive the transform combination corresponding to the MTS index. For example, the decoder may derive or determine the horizontal transform and the vertical transform corresponding to the MTS index.

[0209] Meanwhile, when the number of non-zero transform coefficients is not greater than the threshold, the decoder may apply a preconfigured vertical inverse transform for each column (S1060). For example, the vertical inverse transform may be the inverse transform of the DST7.

[0210] In addition, the decoder may apply a preconfigured horizontal inverse transform for each row (S1070). For example, the horizontal inverse transform may be the inverse transform of the DST7. That is, when the number of non-zero transform coefficients is not greater than the threshold, a transform kernel preconfigured by the encoder or decoder may be used. For example, the transform kernel (e.g., DCT-2) that is not defined in the transform combination table illustrated in FIG. 6 above, but is widely used may be used.

[0211] Meanwhile, when the MTS flag is 0, the decoder may apply the preconfigured vertical inverse transform for each column (S1080). For example, the vertical inverse transform may be the inverse transform of the DCT2.

[0212] In addition, the decoder may apply the preconfigured horizontal inverse transform for each row (S1090). For example, the horizontal inverse transform may be the inverse transform of the DCT2. That is, when the MTS flag is 0, the transform kernel preconfigured in the encoder or decoder may be used. For example, the transform kernel that is not defined in the transform combination table illustrated in FIG. 6 above, but is widely used may be used.

[0213] FIG. 11 is a flowchart of performing an inverse transform based on a transform related parameter as an embodiment to which the present disclosure is applied.

[0214] The decoder to which the present disclosure is applied may obtain sps_mts_intra_enabled_flag or sps_mts_inter_enabled_flag (S1110). In this case, sps_mts_intra_enabled_flag indicates whether tu_mts_flag exists in a residual coding syntax of an intra coding unit. For example, when sps_mts_intra_enabled_flag=0, tu_mts_flag does not exist in the residual coding syntax of the intra coding unit and when sps_mts_intra_enabled_flag=0, tu_mts_flag exists in the residual coding syntax of the intra coding unit. In addition, sps_mts_inter_enabled_flag indicates whether tu_mts_flag exists in the residual coding syntax of the inter coding unit. For example, when sps_mts_inter_enabled_flag=0, tu_mts_flag does not exist in the residual coding syntax of the inter coding unit and when sps_mts_inter_enabled_flag=0, tu_mts_flag exists in the residual coding syntax of the inter coding unit.

[0215] The decoder may obtain tu_mts_flag based on sps_mts_intra_enabled_flag or sps_mts_inter_enabled_flag (S1120). For example, when sps_mts_intra_enabled_flag=1 or sps_mts_inter_enabled_flag=1, the decoder may obtain tu_mts_flag. In this case, tu_mts_flag indicates whether multiple transform selection (hereinafter, referred to as “MTS”) is applied to a residual sample of a luma transform block. For example, when tu_mts_flag=0, the MTS is not applied to the residual sample of the luma transform block and when tu_mts_flag=1, the MTS is applied to the residual sample of the luma transform block.

[0216] As another example, at least one of the embodiments of the present disclosure may be applied to the tu_mts_flag.

[0217] The decoder may obtain mts_idx based on tu_mts_flag (S1130). For example, when tu_mts_flag=1, the decoder may obtain mts_idx. In this case, mts_idx indicates which transform kernel is applied to luma residual samples along the horizontal and/or vertical direction of a current transform block.

[0218] For example, at least one of the embodiments of the present disclosure may be applied to mts_idx. As a specific example, at least one of the embodiments of FIG. 6 above may be applied.

[0219] The decoder may derive the transform kernel corresponding to mts_idx (S1140). For example, the transform kernel corresponding to the mts_idx may be defined by being divided into the horizontal transform and the vertical transform.

[0220] As another example, different transform kernels may be applied to the horizontal transform and the vertical transform. However, the present disclosure is not limited thereto, and the same transform kernel may be applied to the horizontal transform and the vertical transform.

[0221] As an embodiment, mts_idx may be defined as shown in Table 1 below.

[0222]

TABLE 1
mts_idx[x0][y0]	trTypeHor	trTypeVer
0	0	0
1	1	1
2	2	1
3	1	2
4	2	2

[0223] In addition, the decoder may perform the inverse transform based on the transform kernel (S1150).

[0224] In FIG. 11, an embodiment in which in order to determine whether to apply MTS, a transform kernel is determined by obtaining tu_mts_flag and then obtaining mts_idx based on a value of the obtained tu_mts_flag is chiefly described, but the present disclosure is not limited thereto. For example, the decoder may determine a transform kernel by directly parsing mts_idx without tu_mts_flag parsing. In this case, Table 1 may be used. That is, when an mts_idx value indicates 0, DCT-2 may be applied in a horizontal/vertical direction. When an mts_idx value indicates a value other than 0, DST-7 and/or DCT-8 may be applied based on an mts_idx value.

[0225] As another embodiment of the present disclosure, a decoding process of performing the transform process is described.

[0226] The decoder may check a transform size nTbS (S10). In this case, the transform size nTbS may be a variable representing a horizontal sample size of scaled transform coefficients.

[0227] The decoder may check a transform kernel type trType (S20). In this case, the transform kernel type trType may be a variable representing the type of transform kernel and various embodiments of the present disclosure may be applied. The transform kernel type trType may include a horizontal transform kernel type trTypeHor and a vertical transform kernel type trTypeVer.

[0228] Referring to Table 1 above, when the transform kernel type trType is 0, the transform kernel type may represent DCT2, when the transform kernel type trType is 1, the transform kernel type may represent DST7, and when the transform kernel type trType is 2, the transform kernel type may represent DCT8.

[0229] The decoder may perform a transform matrix multiplication based on at least one of the transform size nTbS or the transform kernel type (S30).

[0230] As another example, when the transform kernel type is 1 and the transform size is 4, a predetermined transform matrix 1 may be applied when performing the transform matrix multiplication.

[0231] As another example, when the transform kernel type is 1 and the transform size is 8, a predetermined transform matrix 2 may be applied when performing the transform matrix multiplication.

[0232] As another example, when the transform kernel type is 1 and the transform size is 16, a predetermined transform matrix 3 may be applied when performing the transform matrix multiplication.

[0233] As another example, when the transform kernel type is 1 and the transform size is 32, a predefined transform matrix 4 may be applied when performing the transform matrix multiplication.

[0234] Similarly, when the transform kernel type is 2 and the transform size is 4, 8, 16, or 32, predefined transform matrices 5, 6, 7, and 8 may be applied, respectively.

[0235] In this case, each of the predefined transform matrices 1 to 8 may correspond to any one of various types of transform matrices. As an example, the transform matrix of the type illustrated in FIG. 6 above may be applied.

[0236] The decoder may derive a transform sample based on the transform matrix multiplication (S40).

[0237] The embodiments may be used, but the present disclosure is not limited thereto. The above embodiments and other embodiments of the present disclosure may be combined and used.

[0238] FIG. 12 is a table showing allocation of a transform set for each intra prediction mode in an NSST as an embodiment to which the present disclosure is applied.

Non-Separable Secondary Transform (NSST)

[0239] The secondary transform unit may apply the secondary transform to a primary transformed signal and here, the secondary transform may be defined in the table in the encoder and/or the decoder.

[0240] As an embodiment, the secondary transform may conditionally adopt a non-separable secondary transform (hereinafter, referred to as ‘NSST’). For example, the NSST may be applied only to the intra prediction block and may have a transform set applicable to each prediction mode group.

[0241] In this case, the prediction mode group may be configured based on symmetry with respect to a prediction direction. For example, since prediction mode 52 and prediction mode 16 are symmetrical based on prediction mode 34 (diagonal direction), the same transform set may be applied by forming one group. In this case, when the transform for prediction mode 52 is applied, input data is transposed and then applied because prediction mode 52 has the same transform set as prediction mode 16.

[0242] Meanwhile, since the symmetry for the direction does not exist in the case of a planar mode and a DC mode, each mode may have a different transform set and the corresponding transform set may include two transforms. In respect to the remaining directional modes, each transform set may include three transforms. However, the present disclosure is not limited thereto, and each transform set may include a plurality of transforms.

[0243] FIG. 13 is a calculation flow diagram for Givens rotation as an embodiment to which the present disclosure is applied.

[0244] As another embodiment, the NSST may not be applied to the entire primary transformed block but may be applied only to a top-left 8×8 area. For example, when the block size is 8×8 or more, 8×8 NSST is applied and when the block size is less than 8×8, 4×4 NSST is applied and in this case, the block is divided into 4×4 blocks and then, the 4×4 NSST is applied to each of the divided blocks.

[0245] As another embodiment, even in the case of 4×N/N×4 (N>=16), the 4×4 NSST may be applied.

[0246] Since both the 8×8 NSST and the 4×4 NSST follow a transformation combination configuration described in the present disclosure and are the non-separable transforms, the 8×8 NSST receives 64 data and outputs 64 data and the 4×4 NSST has 16 inputs and 16 outputs.

[0247] Both the 8×8 NSST and the 4×4 NSST are configured by a hierarchical combination of Givens rotations. A matrix corresponding to one Givens rotation is shown in Equation 4 below and a matrix product is shown in Equation 5 below.

[0248] $\begin{array}{cc}{R}_{\theta }=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]& \left[\mathrm{Equation}4\right]\end{array}$ $\begin{array}{cc}{t}_m=x_m\cos \theta -x_n\sin \theta t_n=x_m\sin \theta +x_n\cos \theta & \left[\mathrm{Equation}5\right]\end{array}$

[0249] As illustrated in FIG. 13 above, since one Givens rotation rotates two data, in order to process 64 data (for the 8×8 NSST) or 16 data (for the 4×4 NSST), a total of 32 or 8 Givens rotations are required.

[0250] Therefore, a bundle of 32 or 8 is used to form a Givens rotation layer. Output data for one Givens rotation layer is transferred as input data for a next Givens rotation layer through a determined permutation.

[0251] FIG. 14 illustrates one round configuration in 4×4 NSST constituted by a givens rotation layer and permutations as an embodiment to which the present disclosure is applied.

[0252] Referring to FIG. 14 above, it is illustrated that four Givens rotation layers are sequentially processed in the case of the 4×4 NSST. As illustrated in FIG. 14 above, the output data for one Givens rotation layer is transferred as the input data for the next Givens rotation layer through a determined permutation (i.e., shuffling).

[0253] As illustrated in FIG. 14 above, patterns to be permutated are regularly determined and in the case of the 4×4 NSST, four Givens rotation layers and the corresponding permutations are combined to form one round.

[0254] In the case of the 8×8 NSST, six Givens rotation layers and the corresponding permutations form one round. The 4×4 NSST goes through two rounds and the 8×8 NSST goes through four rounds. Different rounds use the same permutation pattern, but applied Givens rotation angles are different. Accordingly, angle data for all Givens rotations constituting each transform need to be stored.

[0255] As a last step, one permutation is further finally performed on the data output through the Givens rotation layers, and corresponding permutation information is stored separately for each transform. In forward NSST, the corresponding permutation is performed last and in inverse NSST, a corresponding inverse permutation is applied first on the contrary thereto.

[0256] In the case of the inverse NSST, the Givens rotation layers and the permutations applied to the forward NSST are performed in the reverse order and rotation is performed by taking a negative value even for an angle of each Givens rotation.

[0257] FIG. 15 is an embodiment to which the present disclosure is applied, and illustrates a flowchart in which forward DST7 having a length 16 is designed using a discrete Fourier transform (DFT).

[0258] The present disclosure provides detailed embodiments in which DST7 is designed using a DFT. The embodiments of the present disclosure may also be used for a DCT8 design, and may also be applied to an MTS configuration.

[0259] Signals (information) transferred between blocks shown in the flowchart of FIG. 15 may be scalar values and may have a vector form. For example, the vector may be written like x[0 . . . N−1]. This illustrates a signal (information) composed of N elements like x[0 . . . N−1]=[x[0]x[1] . . . x[N−2]x[N−1]]. A partial signal of the vector x[0 . . . N−1] may be indicated like x[i . . . j]. For example, the partial signal may be indicated like x[5 . . . 10]=[x[5]x[6]x[7]x[8]x[9]x[10]] as one part of x[0 . . . 15].

[0260] FIG. 15 illustrates a flowchart in which DST7 is implemented with respect to one row or column of a length 16. In this case, DST7 having the length 16 is written as DST7_B16. Forward DST7 is written as forward DST7_B16. Inverse DST7 is written as inverse DST7_B16.

[0261] Furthermore, input data is x[0 . . . 15], and the final output data may be written as y[0 . . . 15].

[0262] When the input data x[0 . . . 15] is input, the encoder performs pre-processing on forward DST7 having a length 16 (S1510).

[0263] The encoder may apply a DFT to output w[0 . . . 15] at step S1510 (S1520). In this case, the step S1520 of applying the DFT is specifically described with reference to FIGS. 17 to 19.

[0264] The encoder may perform post-processing on output z[0 . . . 15] at step S1520, and may output the final output data y[0 . . . 15](S1530).

[0265] FIG. 16 is an embodiment to which the present disclosure is applied, and illustrates a flowchart in which inverse DST7 having a length 16 is designed using a discrete Fourier transform (DFT).

[0266] FIG. 16 illustrates a flowchart in which inverse DST7 is implemented with respect to one row or column of a length 16. In this case, input data is x[0 . . . 15], and the final output data may be written as y[0 . . . 15].

[0267] When input data x[0 . . . 15] is input, the decoder performs pre-processing on inverse DST7 having a length 16 (S1610).

[0268] The decoder may apply a DFT to an output at step S1610 (S1620). In this case, the step S1620 of applying the DFT is specifically described with reference to FIGS. 17 to 19.

[0269] The decoder may perform post-processing on an output at step S1620, and may output the final output data y[0 . . . 15](S1630).

[0270] FIGS. 17 to 19 are embodiments to which the present disclosure is applied, and illustrate flowcharts in which an xDST7_FFT_B16 function of FIGS. 15 and 16 is applied.

[0271] Referring to FIG. 17, src[0 . . . 15] is input to an xDST7_FFT3 block, and src_FFT11[0 . . . 15] is output (S1710). The outputted src_FFT11[0 . . . 15] may be divided into two partial signals and transmitted.

[0272] For example, the src_FFT11[0 . . . 4] may be transmitted to an xDST7_FFT11_type1 block. The src_FFT11[5 . . . 15] may be transmitted to an xDST7_FFT11_type2 block.

[0273] The xDST7_FFT11 type1 block may receive src_FFT11[0 . . . 4], and outputs dst[0 . . . 4](S1720).

[0274] The xDST7_FFT11 type2 block receives the src_FFT11[5 . . . 15], and outputs dst[5 . . . 15](S1730).

[0275] In this case, an implementation of the xDST7_FFT11 type1 block is specifically described with reference to FIG. 18, and an implementation of the xDST7_FFT11_type2 block is specifically described with reference to FIG. 19.

[0276] Referring to FIG. 18, src[0 . . . 4] is input to an xDST7_FFT11_half1 block, and dst_half1[0 . . . 4] is output (S1810).

[0277] The outputted dst_half1[0 . . . 4] is input to an xDST7_FFT11 type1 block, and dst[0 . . . 4] is output (S1820).

[0278] Referring to FIG. 19, src[0 . . . 10] may be divided into two partial signals and transmitted. For example, the src[0 . . . 4] may be transmitted to an xDST7_FFT11_half1 block. The src[5 . . . 10] may be transmitted to an xDST7_FFT11_half2 block.

[0279] The xDST7_FFT11_half1 block receives the src[0 . . . 4], and outputs dst_half1[0 . . . 4](S1910).

[0280] The xDST7_FFT11_half2 block receives the src[5 . . . 10], and outputs dst_half2[0 . . . 5](S1920).

[0281] The encoder/decoder may perform post-processing on the output at step S1920 through an xDST7_FFT11_type2_Post_Processing block, and may output the final output data dst[0 . . . 10](S1930).

[0282] The src_FFT11[5 . . . 15] of FIG. 17 corresponds to the src[0 . . . 10] of FIG. 19. That is, assignment is performed like src[0]=src_FFT11[5], src[1]=src_FFT11[6], . . . , src[10]=src_FFT11[15].

[0283] Furthermore, in the xDST7_FFT11 type2_Post_Processing block of FIG. 19, dst_half1[0 . . . 4] and dst_half2[0 . . . 5] are sequentially input from the left. They correspond to the input parameters src_half1[0 . . . 4], src_half2[0 . . . 5], respectively. This will be specifically described in a table indicating an operation of each block.

[0284] As described above, the block diagrams of FIGS. 15 and 16 may be connected to the block diagrams of FIGS. 17 to 19 and interpreted.

[0285] Detailed operations of the functions of FIGS. 15 to 19 may be described by Table 2 to Table 10.

[0286]

TABLE 2
Operation of Forward_DST7_Pre_Processing_B16 function
Name	Forward_DST7_Pre_Processing_B16
Input	src[0 . . . 15]
Output	dst[0 . . . 15]
Operation	dst[0] = src[10]; dst[1] = src[8]; dst[2]= src[1]; dst[3] =
	−src[12];
	dst[4] = −src[14]; dst[5] = src[6]; dst[6] = src[3]; dst[7] =
	src[5];
	dst[8] = −src[15]; dst[9] = src[4]; dst[10] = src[2]; dst[11] = src[7];
	dst[12] = −src[13]; dst[13] = −src[11]; dst[14] = src[0]; dst[15] = src[9];

[0287]

TABLE 3
Operation of Forward_DST7_Post_Processing_B16 function
Name	Forward_DST7_Post_Processing_B16
Input	src[0 . . . 15]
Output	dst[0 . . . 15]
Operation	int aiReordIdx[16] = {12, 0, 14, 10, 2, 5, 8, 4, 7, 6,
	3, 9, 15, 1, 11, 13};
	for (int i = 0; i < 16; i++)
	dst[i] = (int)((src[aiReordIdx[i]] + rnd_factor) >> final_shift);

[0288] In Table 3, an rnd_factor=1<<(final_shift-1) value may be used. Furthermore, in FIGS. 15 and 16, when a function for applying DST7 is used for all the rows or columns of one block, if a value called “shift” has been transmitted through a parameter, a final_shift=shift−1 value may be used.

[0289]

TABLE 4
Operation of Inverse_DST7_Pre_Processing_B16 function
Name	Inverse_DST7_Pre_Processing_B16
Input	src[0 . . . 15]
Output	dst[0 . . . 15]
Operation	dst[0] = src[5]; dst[1] = src[4]; dst[2] = src[15]; dst[3] = −src[6];
	dst[4] = −src[7]; dst[5] = src[3]; dst[6] = src[14]; dst[7] = src[13];
	dst[8] = −src[8]; dst[9] = src[2]; dst[10] = src[1]; dst[11] = src[12];
	dst[12] = −src[9]; dst[13] = −src[10]; dst[14] = src[0]; dst[15] = src[11];

[0290]

TABLE 5
Operation of Inverse_DST7_Post_Processing_B16 function
	Name	Inverse_DST7_Post_Processing_B16
	Input	src[0 . . . 15]
	Output	dst[0 . . . 15]
	Operation	int aiReordIdx[16] = {12, 13, 0, 11, 14, 1, 10, 15, 2, 9,
		5, 3, 8, 6, 4, 7};
		for (int i = 0; i < 16; i++)
		dst[i] = Clip3(outputMinimum, outputMaximum, (int)
		((src[aiReordIdx[i]] + rnd_factor) >> final_shift));

[0291] In Table 5, an rnd_factor=1<<(final_shift−1) value may be used. Furthermore, in FIGS. 15 and 16, when a function for applying DST7 to all the rows or columns of one block is used, if a value called “shift” has been transmitted through a parameter, final_shift=shift−1 value may be used.

[0292] In Table 5, outputMinimum and outputMaximum indicate a minimum value and maximum value which may be included in an output value, respectively. The Clip3 function performs an operation of Clip3(A, B, C)=(C<A) ?A: (C>B)?B: C. That is, the Clip3 function clips the C value so that the C value must be present in a range from A to B.

[0293]

TABLE 6
Operation of xDST7_FFT3 function
Name	xDST7_FFT3
Input	src[0 . . . 15]
Output	dst[0 . . . 15]
Operation	int C3 = −443;
	dst[10] = ((−src[0] * C3) + rnd_factor) >> shift;
	for (Int i = 0; i < 5; i++) {
	dst[i] = (((src[3*i + 1] + src[3*i + 2] +
	src[3*i + 3]) << 9) + rnd_factor) >> shift;
	dst[5 + i] = ((((src[3*i + 1] << 1) − src[3*i + 2] −
	src[3*i + 3]) << 8) + rnd_factor) >> shift;
	dst[11 + i] = (((src[3*i + 2] − src[3*i + 3]) * C3) +
	rnd_factor) >> shift;
	}

[0294] In Table 6, a C3 value means a round

[0295] $\left(\sin \left(\frac{2\pi }{3}\right)·2^9\right)$
value, and illustrates a multiplication coefficient has been scaled by 2⁹. In Table 6, since shift=10, rnd_factor=1<(shift−1)=2⁹ is applied, dst[i] and dst[5+i] may be calculated like Equation 6.

[0296] $$\begin{gathered} \begin{array}{cc}\mathrm{dst}\left[i\right]=\left(\mathrm{src}\left[3*i+1\right]+\mathrm{src}\left[3*i+2\right]+\mathrm{src}\left[3*i+3\right]+1\right)>>1 \\ \mathrm{dst}\left[5+i\right]=\left(\left(\mathrm{src}\left[3*i+1\right]<<1\right)-\mathrm{src}\left[3*i+2\right]-\mathrm{src}\left[3*i+3\right]+2\right)>>2& \left[\mathrm{Equation}6\right]\end{array} \end{gathered}$$

[0297]

TABLE 7
Operation of xDST7_FFT11_half1 function
Name	xDST7_FFT11_half1
Input	src[0 . . . 4]
Output	dst[0 . . . 4]
Operation	int C11R[5] = {193, 324, 353, 269, 100};
	dst[0] = src[0] * C11R[1] + src[1] * C11R[3] − src[2] * C11R[4] − src[3] *
	C11R[2] − src[4] * C11R[0];
	dst[1] = src[0] * C11R[2] − src[1] * C11R[4] − src[2] * C11R[1] + src[3] *
	C11R[0] + src[4] * C11R[3];
	dst[2] = −src[0] * C11R[3] + src[1] * C11R[2] − src[2] * C11R[0] − src[3] *
	C11R[4] + src[4] * C11R[1];
	dst[3] = src[0] * C11R[4] − src[1] * C11R[0] + src[2] * C11R[3] − src[3] *
	C11R[1] + src[4] * C11R[2];
	dst[4] = src[0] * C11R[0] + src[1] * C11R[1] + src[2] * C11R[2] + src[3] *
	C11R[3] + src[4] * C11R[4];

[0298] In Table 7, the array C11R illustrates values calculated through round

[0299] $\left(\frac{1}{\sqrt{2\times 16+1}}·\sin \left(\frac{2\pi i}{11}\right)·2^{11}\right),$
i=1, 2, 3, 4, 5.

[0300]

TABLE 8
Operation of xDST7_FFT11_half2 function
Name	xDST7_FFT11_half2
Input	src[0 . . . 5]
Output	dst[0 . . . 5]
Operation	int C11I[6] = {357, 300, 148, −51, −233, −342};
	dst[0] = (src[0] + src[1] + src[2] + src[3] + src[4] + src[5]) * C11I[0];
	dst[1] = src[0] * C11I[0] + src[1] * C11I[2] + src[2] * C11I[4] + src[3] *
	C11I[5] + src[4] * C11I[3] + src[5] * C11I[1];
	dst[2] = src[0] * C11I[0] + src[1] * C11I[3] + src[2] * C11I[5] + src[3] *
	C11I[2] + src[4] * C11I[1] + src[5] * C11I[4];
	dst[3] = src[0] * C11I[0] + src[1] * C11I[4] + src[2] * C11I[3] + src[3] *
	C11I[1] + src[4] * C11I[5] + src[5] * C11I[2];
	dst[4] = src[0] * C11I[0] + src[1] * C11I[5] + src[2] * C11I[1] + src[3] *
	C11I[4] + src[4] * C11I[2] + src[5] * C11I[3];
	dst[5] = src[0] * C11I[0] + src[1] * C11I[1] + src[2] * C11I[2] + src[3] *
	C11I[3] + src[4] * C11I[4] + src[5] * C11I[5];

[0301] In Table 8, the array C11R illustrates values calculated through round

[0302] $\left(\frac{1}{\sqrt{2\times 16+1}}·\cos \left(\frac{2\pi i}{11}\right)·2^{11}\right),$
i=0, 1, 2, 3, 4, 5.

[0303]

TABLE 9
Operation of xDST7_FFT11_type1_Post_Processing function
Name	xDST7_FFT11_type1_Post_Processing
input	src[0 . . . 4]
output	dst[0 . . . 4]
operation	dst[0] = src[4]; dst[1] = −src[0]; dst[2] = src[1];
	dst[3] = src[2]; dst[4] = src[3];

[0304]

TABLE 10
Operation of xDST7_FFT11_type2_Post_Processing function
Name	xDST7_FFT11_type2_Post_Processing
input	src_half1[0 . . . 4], src_half2[0 . . . 5]
output	dst[0 . . . 10]
operation	dst[0] = −src_half2[0];
	dst[1] = src_half2[5] − src_half1[4];
	dst[2] = −(src_half2[1] − src_half1[0]);
	dst[3] = src_half2[2] − src_half1[1];
	dst[4] = −(src_half2[3] + src_half1[2]);
	dst[5] = src_half2[4] − src_half1[3];
	dst[6] = −(src_half2[4] + src_half1[3]);
	dst[7] = src_half2[3] − src_half1[2];
	dst[8] = src_half2[2] + src_half1[1];
	dst[9] = −(src_half2[1] + src_half1[0]);
	dst[10] = src_half2[5] + src_half1[4];

[0305] If DST7 is applied to a 16×16 two-dimensional block in a horizontal direction (or vertical direction), the flowcharts of FIGS. 15 and 16 may be used for 16 rows (or columns).

[0306] FIG. 20 is an embodiment to which the present disclosure is applied, and illustrates a flowchart in which forward DST7 having a length 32 is designed using a discrete Fourier transform (DFT).

[0307] The present disclosure provides detailed embodiments in which DST7 is designed using a DFT. The embodiments of the present disclosure may also be used for a DCT8 design, and may also be applied to an MTS configuration.

[0308] FIG. 20 illustrates a flowchart in which DST7 is implemented with respect to one row or column of a length 32. In this case, the DST7 having the length 32 is written as DST7_B32, forward DST7 is written as forward DST7_B32, and inverse DST7 is written as inverse DST7_B32.

[0309] Furthermore, input data is x[0 . . . 31], and the final output data may be written as y[0 . . . 31].

[0310] When the input data x[0 . . . 31] is input, the encoder performs pre-processing on the forward DST7 having the length 32 (S2010).

[0311] The encoder may apply a DFT to output w[0 . . . 31] at step S2010 (S2020). In this case, step S2020 of applying the DFT is specifically described with reference to FIGS. 22 to 24.

[0312] The encoder may perform post-processing on an output z[0 . . . 31]) at step S2020, and may output the final output data y[0 . . . 31](S2030).

[0313] FIG. 21 is an embodiment to which the present disclosure is applied, and illustrates a flowchart in which forward DST7 having a length 32 is designed using a discrete Fourier transform (DFT).

[0314] FIG. 21 illustrates a flowchart in which inverse DST7 is implemented with respect to one row or column of a length 32. In this case, input data is x[0 . . . 31], and the final output data may be written as y[0 . . . 31].

[0315] When the input data x[0 . . . 31] is input, the decoder performs pre-processing on forward DST7 having a length 32 (S2110).

[0316] The decoder may apply a DFT to an output w[0 . . . 31] at step S2110 (S2120). In this case, step S2120 of applying the DFT is specifically described with reference to FIGS. 22 to 24.

[0317] The decoder may perform post-processing on an output z[0 . . . 31] at step S2120, and may output the final output data y[0 . . . 31](S2130).

[0318] FIGS. 22 to 24 are embodiments to which the present disclosure is applied, and illustrates a flowchart in which the xDST7_FFT_B16 function of FIGS. 15 and 16 is applied.

[0319] Referring to FIG. 22, src[0 . . . 31] is input to an xDST7_FFT5 block, and src_FFT13[0 . . . 31] is output (S2210). The outputted src_FFT13[0 . . . 31] may be divided into three partial signals and transmitted.

[0320] For example, the src_FFT13[0 . . . 5] may be transmitted to an xDST7_FFT13_type1 block, the src_FFT13[6 . . . 18] may be transmitted to an xDST7_FFT13 type2 block, and the src_FFT13[19 . . . 31] may be transmitted to another xDST7_FFT13 type2 block.

[0321] The xDST7_FFT13 type1 block receives the src_FFT13[0 . . . 5], and outputs dst[0 . . . 5](S2220).

[0322] The xDST7_FFT13 type2 block receives the src_FFT13[6 . . . 18], and outputs dst[6 . . . 31](S2230).

[0323] The xDST7_FFT13 type2 block receives the src_FFT13[19 . . . 31], and outputs dst[19 . . . 31](S2240).

[0324] In this case, an implementation of the xDST7_FFT13 type1 block is specifically described with reference to FIG. 23, and an implementation of the xDST7_FFT13 type2 block is specifically described with reference to FIG. 24.

[0325] Referring to FIG. 23, src[0 . . . 5] is input to an xDST7_FFT13_half1 block, and dst_half1[0 . . . 5] is output (S2310).

[0326] The outputted dst_half1[0 . . . 5] is input to an xDST7_FFT13 type1_Post_Processing block, which outputs dst[0 . . . 5](S2320).

[0327] Referring to FIG. 24, src[0 . . . 12] may be divided into two partial signals and transmitted. For example, the src[0 . . . 5] may be transmitted to an xDST7_FFT13_half1 block, and the src[6 . . . 12] may be transmitted to an xDST7_FFT13_half2 block.

[0328] The xDST7_FFT13_half1 block receives the src [0 . . . 5], and outputs dst_half1[0 . . . 5](S2410).

[0329] The xDST7_FFT13_half2 block receives the src[6 . . . 12], and outputs dst_half2 [0 . . . 6](S2420).

[0330] The encoder/decoder may perform post-processing the outputs at steps S2410 and S2420 through an xDST7_FFT13 type2_Post_Processing block, and may output the final output data dst[0 . . . 12](S1930).

[0331] src_FFT 13[0 . . . 5] of FIG. 22 corresponds to src[0 . . . 5] of FIG. 23. That is, assignment is performed like src[0]=src_FFT13[0], src[1]=src_FFT13[1], . . . , src[5]=src_FFT13[5].

[0332] Furthermore, src_FFT13[6 . . . 18] or src_FFT13[19 . . . 31] of FIG. 22 corresponds to src[0 . . . 12] of FIG. 24. For example, assignment is performed like src[0]=src_FFT13[6], src[1]=src_FFT13[7], . . . , src[12]=src_FFT13[18].

[0333] Furthermore, in the xDST7_FFT13 type2_Post_Processing block of FIG. 24, dst_half1[0 . . . 5] and dst_half2[0 . . . 6] are sequentially input from the left. They correspond to input parameters src_half1[0 . . . 5], src_half2[0 . . . 6], respectively. This will be specifically described in a table indicating an operation of each block.

[0334] As described above, the block diagrams of FIGS. 20 and 21 may be connected to the block diagrams of FIGS. 22 to 24 and interpreted.

[0335] Detailed operations of the functions of FIGS. 20 to 24 may be described by Table 11 to Table 18 below.

[0336]

TABLE 11
Operation of Forward_DST7_Pre_Processing_B32 function
Name	Forward_DST7_Pre_Processing_B32
Input	src[0 . . . 31]
Output	dst[0 . . . 31]
Operation	int aiFFTInReordIdx[32] = {12, 25, −14, 1, 10, −23, 27,
	29, −16, 3, 8, −21, −19, 31, −18, 5, 6, 4, −17, 30, −20,
	7, 9, 2, −15, 28, −22, −24, 11, 0, −13, 26};
	for (int i = 0; i < 32; i++) {
	int index = aiFFTInReordIdx[i];
	dst[i] = (index < 0) ? −src[−index]: src[index];
	}

[0337]

TABLE 12
Operation of Forward_DST7_Post_Processing_B32 function
Name	Forward_DST7_Post_Processing_B32
Input	src[0 . . . 31]
Output	dst[0 . . . 31]
Operation	int aiFFTOutReordIdx[32] = {−27, −17, 0, 15, 25, −29, −6, 2, 13, 23, −31,
	−8, 4, 11, 21, −20, −10, 5, 9, 19, −22, −12, 3, 7, 30, −24, −14, 1, 18, 28, −26,
	−16};
	for (int i = 0; i < 32; i++) {
	int index = aiFFTOutReordIdx[i];
	dst[i] = (int)((((index < 0) ? −src[−index]: src[index]) + rnd_factor) >>
	final_shift);
	}

[0338] In Table 12, an rnd_factor=1<K (final_shift−1) value may be used. Furthermore, in FIGS. 20 and 21, when a function for applying DST7 to all the rows or columns of one block, if a value called “shift” has been transmitted through a parameter, final_shift=shift−1 value may be used.

[0339]

TABLE 13
Operation of Inverse_DST7_Pre_Processing_B32 function
Name	Inverse_DST7_Pre_Processing_B32
Input	src[0 . . . 31]
Output	dst[0 . . . 31]
Operation	int aiFFTInReordIdx[32] = {6, 19, −7, 31, 5, −20, 18, 17, −8, 30, 4, −21,
	−22, 16, −9, 29, 3, 2, −23, 15, −10, 28, 27, 1, −24, 14, −11, −12, 26, 0, −25,
	13};
	for (int i = 0; i < 32; i++) {
	int index = aiFFTInReordIdx[i];
	dst[i] = (index < 0) ? −src[−index]: src[index];
	}

[0340]

TABLE 14
Operation of Inverse_DST7_Post_Processing_B32 function
Name	Inverse_DST7_Post_Processing_B32
Input	src[0 ... 31]
Output	dst[0 ... 31]
Operation	int aiFFTOutReordIdx[32] = {−27, −16, −17, −26, 0, 28, 15, 18, 25, 1, −29, −14, −
	6, −24, 2, 30, 13, 7, 23, 3, −31, −12, −8, −22, 4, 19, 11, 9, 21, 5, −20, −10};
	for (int i = 0; i < 32; i++) {
	int index = aiFFTOutReordIdx[i];
	dst[i] = Clip3(outputMinimum, outputMaximum, (Int)((((index < 0) ? −src[−
	index]: src[index]) + rnd_factor) >> final_shift));
	}

[0341] In Table 14, an rnd_factor=1<K (final_shift−1) value may be used. Furthermore, in FIGS. 20 and 21, when a function for applying DST7 to all the rows or columns of one block, if a value called “shift” has been transmitted through a parameter, final_shift=shift−1 value may be used.

[0342] In Table 14, outputMinimum and outputMaximum indicate a minimum value and a maximum value which may be included in an output value, respectively. The Clip3 function performs an operation of Clip3(A, B, C)=(C<A)?A: (C>B)?B: C. That is, the Clip3 function clips the C value so that the C value must be present in a range from A to B.

[0343]

TABLE 15
Operation of xDST7_FFT13_half1 function
Name	xDST7_FFT13_half1
Input	src[0 ... 5]
Output	dst[0 ... 5]
Operation	Int C13R[6] = {167, 296, 357, 336, 238, 86};
	dst[0] = −src[0] * C13R[0] − src[1] * C13R[1] − src[2] * C13R[2] − src[3] *
	C13R[3] − src[4] * C13R[4] − src[5] * C13R[5];
	dst[1] = −src[0] * C13R[1] − src[1] * C13R[3] − src[2] * C13R[5] + src[3] *
	C13R[4] + src[4] * C13R[2] + src[5] * C13R[0];
	dst[2] = −src[0] * C13R[2] − src[1] * C13R[5] + src[2] * C13R[3] + src[3] *
	C13R[0] − src[4] * C13R[1] − src[5] * C13R[4];
	dst[3] = −src[0] * C13R[3] + src[1] * C13R[4] + src[2] * C13R[0] − src[3] *
	C13R[2] + src[4] * C13R[5] + src[5] * C13R[1]
	dst[4] = −src[0] * C13R[4] + src[1] * C13R[2] − src[2] * C13R[1] + src[3] *
	C13R[5] + src[4] * C13R[0] − src[5] * C13R[3];
	dst[5] = −src[0] * C13R[5] + src[1] * C13R[0] − src[2] * C13R[4] + src[3] *
	C13R[1] − src[4] * C13R[3] + src[5] * C13R[2];

[0344] In Table 15, the array C13R illustrates values calculated through round

[0345] $\left(\frac{1}{\sqrt{2\times 32+1}}·\sqrt{2}·\sin \left(\frac{2\pi i}{13}\right)·2^{11}\right),$
i=1, 2, 3, 4, 5, 6.

[0346]

TABLE 16
Operation of xDST7_FFT13_half2 function
Name	xDST7_FFT13_half2
Input	src[0 ... 6]
Output	dst[0 ... 6]
Operation	int C13I[7] = {359, 318, 204, 43, −127, −269, −349};
	dst[0] = (src[0] + src[1] + src[2] + src[3] + src[4] + src[5] + src[6]) * C13I[0];
	dst[1] = src[0] * C13I[0] + src[1] * C13I[1] + src[2] * C13I[2] + src[3] *
	C13I[3] + src[4] * C13I[4] + src[5] * C13I[5] + src[6] * C13I[6];
	dst[2] = src[0] * C13I[0] + src[1] * C13I[2] + src[2] * C13I[4] + src[3] *
	C13I[6] + src[4] * C13I[5] + src[5] * C13I[3] + src[6] * C13I[1];
	dst[3] = src[0] * C13I[0] + src[1] * C13I[3] + src[2] * C13I[6] + src[3] *
	C13I[4] + src[4] * C13I[1] + src[5] * C13I[2] + src[6] * C13I[5];
	dst[4] = src[0] * C13I[0] + src[1] * C13I[4] + src[2] * C13I[5] + src[3] *
	C13I[1] + src[4] * C13I[3] + src[5] * C13I[6] + src[6] * C13I[2];
	dst[5] = src[0] * C13I[0] + src[1] * C13I[5] + src[2] * C13I[3] + src[3] *
	C13I[2] + src[4] * C13I[6] + src[5] * C13I[1] + src[6] * C13I[4];
	dst[6] = src[0] * C13I[0] + src[1] * C13I[6] + src[2] * C13I[1] + src[3] *
	C13I[5] + src[4] * C13I[2] + src[5] * C13I[4] + src[6] * C13I[3];

[0347] In Table 16, the array C13e illustrates values calculated through round

[0348] $\left(\frac{1}{\sqrt{2\times 32+1}}·\sqrt{2}·\cos \left(\frac{2\pi i}{13}\right)·2^{11}\right),$
i=0, 1, 2, 3, 4, 5, 6.

[0349]

TABLE 17
Operation of xDST7_FFT13_type1_Post_Processing function
Name	xDST7_FFT 13_type1_Post_Processing
Input	src[0 ... 5]
Output	dst[0 ... 5]
Operation	dst[0] = −src[0]; dst[1] = src[1]; dst[2] = −src[2];
	dst[3] = src[3]; dst[4] = −src[4]; dst[5] = src[5];

[0350]

TABLE 18
Operation of xDST7_FFT13_type2_Post_Processing function
Name	xDST7_FFT13_type2_Post_Processing
Input	src_half1[0 ... 5], src_half2[0 ... 6]
Output	dst[0 ... 12]
Operation	dst[0] = src_half2[0];
	for (int i = 0; i < 6; i++) {
	dst[1 + i] = src_half1[i] + src_half2[1 + i];
	}
	for (int i = 0; i < 6; i++) {
	dst[7 + i] = −src_half1[5 − i] + src_half2[6 − i];
	}

[0351] If DST7 is applied to one 32×32 two-dimensional block in a horizontal direction (or vertical direction), the flowcharts of FIGS. 20 and 21 may be used for 32 rows (or columns).

[0352] FIG. 25 is an embodiment to which the present disclosure is applied, and illustrates a flowchart in which forward DST7 having a length 8 is designed using a discrete Fourier transform (DFT).

[0353] The present disclosure provides detailed embodiments in which DST7 is designed using a DFT. The embodiments of the present disclosure may also be used for a DCT8 design, and may also be applied to an MTS configuration.

[0354] FIG. 25 illustrates a flowchart in which DST7 is implemented with respect to one row or column of a length 8. In this case, the DST7 having the length 8 is written as DST7_B8, forward DST7 is written as forward DST7_B8, and inverse DST7 is written as inverse DST7_B8.

[0355] Furthermore, input data is x[0 . . . 7], and the final output data may be written as y[0 . . . 7].

[0356] When the input data x[0 . . . 7] is input, the encoder performs pre-processing on forward DST7 having a the length 8 (S2510).

[0357] The encoder may apply a DFT to an output w[0 . . . 7] at step S2510 (S2520). In this case, step S2520 of applying the DFT is specifically described with reference to FIGS. 27 and 28.

[0358] The encoder may perform post-processing on the output z[0 . . . 7]) at step S2520, and may output the final output data y[0 . . . 7](S2530).

[0359] FIG. 26 is an embodiment to which the present disclosure is applied, and illustrates a flowchart in which inverse DST7 having a length 8 is designed using a discrete Fourier transform (DFT).

[0360] FIG. 26 illustrates a flowchart in which inverse DST7 is implemented with respect to one row or column of a length 8. In this case, input data is x[0 . . . 7], and the final output data may be written as y[0 . . . 7].

[0361] When the input data x[0 . . . 7] is input, the decoder performs pre-processing on inverse DST7 having a length 8 (S2610).

[0362] The decoder may apply a DFT to an output w[0 . . . 7] at step S2610 (S2620). In this case, step S2620 of applying the DFT is specifically described with reference to FIGS. 27 and 28.

[0363] The decoder may perform post-processing on an output z[0 . . . 7] at step S2620, and may output the final output data y[0 . . . 7](S2630).

[0364] Detailed operations of the functions of FIGS. 25 and 26 may be described by Table 19 to Table 23 below.

[0365]

TABLE 19
Operation of Forward_DST7_Pre_Processing_B8 function
Name	Forward_DST7_Pre_Processing_B8
Input	src[0 ... 7]
Output	dst[0 ... 7]
Operation	dst[0] = src[1]; dst[1] = src[5]; dst[2] = −src[0]; dst[3] = −src[2];
	dst[4] = −src[7]; dst[5] = src[6]; dst[6] = −src[3]; dst[7] = −src[4]

[0366]

TABLE 20
Operation of Forward_DST7_Post_Processing_B8 function
Name	Forward_DST7_Post_Processing_B8
Input	src[0 ... 7]
Output	dst[0 ... 7]
Operation	int aiReordIdx[8] = {0, 2, 4, 6, 7, 5, 3, 1};
	for (int i = 0; i < 8; i++) {
	dst[i] = (int)((src[aiReordIdx[i]] + rnd_factor) >> shift);
	}

[0367] In Table 20, an rnd_factor=1<<(shift−1) value may be used. In this case, a shift value is a value transferred through a parameter when a function for applying DST7 to all the rows or columns of one block is used.

[0368]

TABLE 21
Operation of Inverse_DST7_Pre_Processing_B8 function
Name	Inverse_DST7_Pre_Processing_B8
Input	src[0 ... 7]
Output	dst[0 ... 7]
Operation	dst[0] = src[7]; dst[1] = src[5]; dst[2] = −src[0]; dst[3] = −src[1];
	dst[4] = −src[4]; dst[5] = src[3]; dst[6] = −src[6]; dst[7] = −src[2];

[0369]

TABLE 22
Operation of Inverse_DST7_Post_Processing_B8 function
Name	Inverse_DST7_Post_Processing_B8
input	src[0 ... 7]
output	dst[0 ... 7]
operation	for (Int i = 0; i < 8; i++) {
	dst[i] = Clip3(outputMinimum, outputMaximum, (Int)((src[i]) + rnd_factor)
	>> shift);
	}

[0370] In Table 22, an rnd_factor=1<K (shift−1) value may be used. In this case, a shift value is a value transferred through a parameter when a function for applying DST7 to all the rows or columns of one block is used.

[0371] In Table 5, outputMinimum and outputMaximum indicate a minimum value and a maximum value which may be included in an output value, respectively. The Clip3 function performs an operation of Clip3(A, B, C)=(C<A)?A: (C>B)?B: C. That is, the Clip3 function clips the C value so that the C value must be present in a range from A to B.

[0372]

TABLE 23
Operation of xDST7_FFT_B8 function
Name	xDST7_FFT_B8
Input	src[0 ... 7]
Output	dst[0 ... 7]
Operation	int C8[8] = {127, 237, 314, 350, 338, 280, 185, 65};
	dst[0] = src[0] * C8[0] + src[1] * C8[2] − src[2] * C8[7] − src[3] * C8[6] − src[4]
	* C8[3] + src[5] * C8[4] − src[6] * C8[1] − src[7] * C8[5];
	dst[1] = −src[0] * C8[1] − src[1] * C8[5] − src[2] * C8[0] − src[3] * C8[2] +
	src[4] * C8[7] + src[5] * C8[6] + src[6] * C8[3] − src[7] * C8[4];
	dst[2] = src[0] * C8[2] − src[1] * C8[7] − src[2] * C8[6] − src[3] * C8[3] + src[4]
	* C8[4] − src[5] * C8[1] − src[6] * C8[5] − src[7] * C8[0];
	dst[3] = −src[0] * C8[3] + src[1] * C8[4] − src[2] * C8[1] − src[3] * C8[5] −
	src[4] * C8[0] − src[5] * C8[2] + src[6] * C8[7] + src[7] * C8[6];
	dst[4] = src[0] * C8[4] − src[1] * C8[1] − src[2] * C8[5] − src[3] * C8[0] − src[4]
	* C8[2] + src[5] * C8[7] + src[6] * C8[6] + src[7] * C8[3];
	dst[5] = −src[0] * C8[5] − src[1] * C8[0] − src[2] * C8[2] + src[3] * C8[7] +
	src[4] * C8[6] + src[5] * C8[3] − src[6] * C8[4] + src[7] * C8[1];
	dst[6] = src[0] * C8[6] + src[1] * C8[3] − src[2] * C8[4] + src[3] * C8[1] +
	src[4] * C8[5] + src[5] * C8[0] + src[6] * C8[2] − src[7] * C8[7];
	dst[7] = −src[0] * C8[7] − src[1] * C8[6] − src[2] * C8[3] + src[3] * C8[4] −
	src[4] * C8[1] − src[5] * C8[5] − src[6] * C8[0] − src[7] * C8[2];

[0373] In Table 23, the array C8 illustrates values calculated through round

[0374] $\left(\frac{1}{\sqrt{2\times 8+1}}·\sqrt{2}·\sin \left(\frac{2\pi i}{17}\right)·2^{10}\right),$
i=1, 2, 3, 4, 5, 6, 7, 8.

[0375] If DST7 is applied to an 8×8 two-dimensional block in a horizontal direction (or vertical direction), the flowcharts of FIGS. 25 and 26 may be used for eight rows (or columns).

[0376] The DST7 implementations proposed in Embodiment 1 and Embodiment 2 may be applied to DST7 having a length 16 and DST7 having a length 32. The DST7 implementation proposed in Embodiment 3 may be applied to DST7 having a length 8, but the present disclosure is not limited thereto, and may be differently applied. For example, if the DST7 implementation proposed in Embodiment 3 is not applied, a DST7 implementation having a common matrix multiplication form may be applied.

[0377] A matrix form of N×N DST7 may be represented like Equation 7.

[0378] $\begin{array}{cc}& \left[\mathrm{Equation}7\right]\end{array}$ ${\left[S_N^{\mathrm{VII}}\right]}_{n,k}=\frac{2}{\sqrt{2N+1}}\sin \left(\frac{\pi \left(2k+1\right)\left(n+1\right)}{2N+1}\right),n,k=0,1,\dots ,N-1$

[0379] In this case, if n is a row index from 0 to N−1 and k is a column index from 0 to N−1, the matrix of Equation 7 is matched with an inverse DST7 matrix multiplied by transform coefficients in order to reconstruct the original inputs.

[0380] Accordingly, the transpose matrix of Equation 7 is a forward DST7 matrix. Furthermore, forward DST7 and inverse DST7 matrices are orthogonal to each other, and each of default vectors thereof has norm 1.

[0381] A relation between the DST7 and the DFT may be represented like Equation 8 based on Equation 7.

[0382] $\begin{array}{cc}{\left(S_N^{\mathrm{VII}}\right)}^T=R\left[F_{2N+1}\right]\mathrm{QP}& \left[\mathrm{Equation}8\right]\end{array}$ ${\mathrm{where}\left[R\right]}_{n,k}=\{\begin{array}{cc}-1,& \mathrm{if}k=2n+1,n=0,1,\dots ,N-1\\ 0,& \mathrm{otherwise}\end{array},$ $Q=\left(\begin{array}{c}{0}^T\\ I_N\\ -J_N\end{array}\right),$ ${\mathrm{and}\left[P\right]}_{n.k}=\{\begin{array}{ccc}1,& \mathrm{if}k+1=2\left(n+1\right),& n=0,1,\dots ,N/2-1\\ 1,& \mathrm{if}k+1=2\left(N-n\right)-1,& n=N/2,\dots ,N-1\\ 0,& \mathrm{otherwise}& \end{array}$

[0383] In Equation 8, R is an N×(2N+1) matrix (the number of rows×the number of columns), Q is an (2N+1)×N matrix, and P is an N×N matrix. I_N indicates an N×N identity matrix, and J_N indicates

[0384] ${\left[J_N\right]}_{\mathrm{ij},i,j=0,\dots ,N-1}=\{\begin{array}{cc}1,& j=N-1-i\\ 0,& \mathrm{otherwise}\end{array}.$

[0385] In Equation 8, [F_2N+1] means that only the imaginary part of DFT results is taken after a DFT having a length (2N+1) is performed. Equation 8 is held only when N is an even number. More specifically, the [F_2N+1] means that when x input as forward DST7 is an N×1 vector, if z=QPx is calculated, an (2N+1)×1 vector(z) is output, and only a next imaginary part on which a DFT having a 2N+1 length is performed using a vector (z) as an input is taken.

[0386] As in Equation 8, the rearranging of N inputs and the assigning of their signs (+/−) are performed on matrices P, Q, and R so that major calculation parts become a 2N+1 length DF in forward DST7.

[0387] The present disclosure uses DST7 having a 2n×2n (N=2n) size. Accordingly, 9-point DFT, 17-point DFT, 33-point DFT, and 65-point DFTs may be applied when N=4, 8, 16, 32, respectively.

[0388] The present disclosure chiefly describes a case where N=8, 16, 32, and provides a method of introducing the design of corresponding DFTs in the form of an equivalent multi-dimensional DFT and integrating the DFTs in order to obtain low complexity DST7.

[0389] inverse N×N DST7 matched with forward DST6 may be represented as 2N+1 length DFT as in Equation 9:

[0390] $\begin{array}{cc}{\left(S_N^{\mathrm{VII}}\right)}^T=R\left[F_{2N+1}\right]\mathrm{QP},& \left[\mathrm{Equation}9\right]\end{array}$ ${\mathrm{where}\left[R\right]}_{n,k}=\{\begin{array}{cc}1,& \mathrm{if}k=n+1,n-1,3,\dots ,N-1\\ -1,& \mathrm{if}k=n+1,n=0,2,\dots ,N-2\\ 0,& \mathrm{otherwise}\end{array},$ $Q=\left(\begin{array}{c}{0}^T\\ I_N\\ -J_N\end{array}\right),{\mathrm{and}\left[P\right]}_{n,k}=\{\begin{array}{cc}1,& \mathrm{if}k=n,n=0,1,\dots ,N-1\\ 0,& \mathrm{otherwise}\end{array}$

[0391] In this case, R is an N×(2N+1) matrix (the number of rows×the number of columns), Q is a (2N+1)×N matrix, and I_N indicates an N×N identity matrix. The definition of J_N is the same as that in Equation 8.

[0392] [F_2N+1] means that when x input as forward DST7 is an N×1 vector, if z=Qx is calculated, a (2N+1)×1 vector(z) is output, and only a next imaginary part on which a DFT having a 2N+1 length is performed using the vector (z) as an input is taken. That is, the meaning of [F_2N+1] in Equation 9 is the same as the definition in Equation 8 except that z=QPx is calculated.

[0393] In Equation 9, N is an even number. Furthermore, the same 2N+1 length DFT as that in forward DST7 may be used in inverse DST7.

[0394] A trigonometric transform having a length of an even number may be applied to a codec system to which the present disclosure is applied. For example, DFTs having lengths 17, 33, 65, and 129 from Equation 8 are necessary for DST7s having lengths 8, 16, or 32 and 64, respectively. A 33-point DFT and a 65-point DFT which may be applied to the DST7 having the lengths 8 and 16 may be represented as one-dimensional DFTs as in Equation 10 and Equation 11. Equation 12 illustrates a DFT equation for a common length N.

[0395] $\begin{array}{cc}X\left(k\right)=\frac{1}{\sqrt{2·16+1}}\sum _{n=0}^{32}x\left(n\right)W_N^{\mathrm{nk}},W_N=e^{-j\left(2\pi /33\right)}& \left[\mathrm{Equation}10\right]\end{array}$ $\begin{array}{cc}X\left(k\right)=\frac{1}{\sqrt{2·32+1}}\sum _{n=0}^{64}x\left(n\right)W_N^{\mathrm{nk}},W_N=e^{-j\left(2\pi /65\right)}& \left[\mathrm{Equation}11\right]\end{array}$ $\begin{array}{cc}X\left(k\right)=\frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}x\left(n\right)W_N^{\mathrm{nk}},W_N=e^{-j\left(2\pi /M\right)}& \left[\mathrm{Equation}12\right]\end{array}$

[0396] For an N×N DST7 implementation, a process of applying a DFT having a length 2N+1 has been described. However, a length N instead of the length 2N+1 may be used for contents including Equations 10 and 11 for convenience of writing. Accordingly, if a DFT is applied through Equations 8 and 9, there is a need for a transform in proper writing.

[0397] Furthermore, the one-dimensional 33-point DFT and the one-dimensional 65-point DFT are also represented as equivalent two-dimensional DFTs through a simple input/output data transform, and corresponding equations thereof are the same as Equations 13 and 14.

[0398] $\begin{array}{cc}& \left[\mathrm{Equation}13\right]\end{array}$ $\widehat{X}\left(k_1,k_2\right)=\frac{1}{\sqrt{2·16+1}}\sum _{n_2=0}^{10}\sum _{n_1=0}^2\widehat{x}\left(n_1,n_2\right)W_3^{n_1{k}_1}{W}_{11}^{n_2{k}_2}=\sum _{n_2=0}^{10}\widehat{y}\left(k_1,n_2\right)W_{11}^{n_2{k}_2}$ $\begin{array}{cc}& \left[\mathrm{Equation}14\right]\end{array}$ $\widehat{X}\left(k_1,k_2\right)=\frac{1}{\sqrt{2·32+1}}\sum _{n_2=0}^{12}\sum _{n_1=0}^4\widehat{x}\left(n_1,n_2\right)W_5^{n_1{k}_1}{W}_{13}^{n_2{k}_2}=\sum _{n_2=0}^{12}\widehat{y}\left(k_1,n_2\right)W_{13}^{n_2{k}_2}$

• • [0399] wherein n indicates an index for input data, and k indicates an index for a transform coefficient.

[0400] Hereinafter, a residue of a number is written as x_N=x mod N. Furthermore, four index variables n₁, n₂, k₁, and k₂ are introduced, and a relation between a 33-point DFT and a 65-point DFT may be indicated like Equations 15 and 16.

[0401] $\begin{array}{cc}n={\langle 22n_1+12n_2\rangle }_{33}& \left[\mathrm{Equation}15\right]\end{array}$ $k={\langle 11k_1+3k_2\rangle }_{33}$ $\begin{array}{cc}n={\langle 26n_1+40n_2\rangle }_{65}& \left[\mathrm{Equation}16\right]\end{array}$ $k={\langle 13k_1+5k_2\rangle }_{65}$

• • [0402] wherein n indicates an index for input data, and k indicates an index for a transform coefficient. Equation 15 indicates an index mapped to a 33-point DFT, and Equation 16 indicates an index mapped to a 65-point DFT.

[0403] Input/output data mapping between a one-dimensional DFT and a two-dimensional DFT is given like Equations 17 and 18 according to Equations 15 and 16. In the present disclosure, new input/output variables may be defined as two index arguments {circumflex over (x)}(n₁, n₂) and {circumflex over (X)}(k₁, k₂) like Equations 17 and 18 from Equations 15 and 16.

[0404] $\begin{array}{cc}\widehat{x}\left(n_1,n_2\right)=x\left({\langle 22n_1+12n_2\rangle }_{33}\right)& \left[\mathrm{Equation}17\right]\end{array}$ $\widehat{X}\left(k_1,k_2\right)=X\left({\langle 11k_1+3k_2\rangle }_{33}\right)$ $\begin{array}{cc}\widehat{x}\left(n_1,n_2\right)=x\left({\langle 26n_1+40n_2\rangle }_{65}\right)& \left[\mathrm{Equation}18\right]\end{array}$ $\widehat{X}\left(k_1,k_2\right)=X\left({\langle 13k_1+5k_2\rangle }_{65}\right)$

• • [0405] wherein x_N=x mod N.

[0406] A two-dimensional DFT has been enabled by Equations 15 and 17, but the present disclosure is not limited thereto. That is, if Equation 19 is satisfied, two-dimensional DFTs, such as Equations 13 and 14, may be formed.

[0407] $\begin{array}{cc}N=N_1{N}_2& \left[\mathrm{Equation}19\right]\end{array}$ $n={\langle K_1{n}_1+K_2{n}_2\rangle }_N$ $k={\langle K_3{k}_1+K_4{k}_2\rangle }_N$ ${\langle K_1{K}_3\rangle }_N=N_2$ ${\langle K_2{K}_4\rangle }_N=N_1$ ${\langle K_1{K}_4\rangle }_N={\langle K_2{K}_3\rangle }_N=0$

• • [0408] wherein N₁ and N₂ indicate mutually prime factors. Furthermore, x_N x mod N.

[0409] A 33-point one-dimensional DFT corresponds to (N₁, N₂)=(3, 11), and a 65-point one-dimensional DFT corresponds to (N₁, N₂)=(5, 13). In both cases, since both N₁ and N₂ are mutually prime factors, Equation 19 may be applied. If K₁, K₂, K₃, and K₄ satisfy Equation 20, in Equation 19, the K₁K_4N K₂K_3N=0 condition is satisfied.

[0410] $\begin{array}{cc}{K}_1=\alpha N_2,K_2=\beta N_1,K_3=\gamma N_2,K_4=\delta N_1& \left[\mathrm{Equation}20\right]\end{array}$

[0411] Furthermore, in order to satisfy other conditions of Equation 19, a relation equation of Equation 21 needs to be satisfied.

[0412] $\begin{array}{cc}{\langle \alpha \gamma N_2\rangle }_{N_1}=1,{\langle \beta \delta N_1\rangle }_{N_2}=1& \left[\mathrm{Equation}21\right]\end{array}$

[0413] Accordingly, all α, β, γ, δ to satisfy Equation 21 can derive K₁, K₂, K₃, and K₄ to satisfy Equation 19 from Equation 20, enabling an equivalent two-dimensional DFT to be constructed. Possible embodiments of α, β, γ, δ are as follows.

• • [0414] 1) (α, β, γ, δ)=(2, 4, 1, 1)

[0415] This corresponds to Equation 15 and is a case where (N₁, N₂)=(3, 11).

• • [0416] 2) (α, β, γ, δ)=(2, 8, 1, 1)

[0417] This corresponds to Equation 16 and is a case where (N₁, N₂)=(5, 13).

• • [0418] 3) (α, β, γ, δ)=(1, 1, 2, 4)

[0419] This is a case where (N₁, N₂)=(3, 11).

• • [0420] 4) (α, β, γ, δ)=(1, 1, 2, 8)

[0421] This is a case where (N₁, N₂)=(5, 13).

[0422] If a corresponding two-dimensional DFT is configured by K₁, K₂, K₃, and K₄ derived from α, β, γ, δ that satisfies Equation 21, in a process of calculating the two-dimensional DFT, symmetries between input/output data and intermediate result values, such as those in the equations, may occur.

[0423] Accordingly, even in the case of a two-dimensional DFT having indices (i.e., having different α, β, γ, δ values) different from those of the embodiments, as a result, complexity necessary to perform DST7 can be significantly reduced by applying the method and structure proposed in the embodiments.

[0424] In summary, a DFT for a length N (N=N₁N₂, N₁ and N₂ are mutually prime factors) may be calculated as a two-dimensional DFT, such as Equation 22, by index transform (i.e., a transform between a one-dimensional index and a two-dimensional index) that satisfies Equations 19 to 21.

[0425] $\begin{array}{cc}& \left[\mathrm{Equation}22\right]\end{array}$ $\widehat{X}\left(k_1,k_2\right)=\frac{1}{\sqrt{N}}\sum _{n_2=0}^{N_2-1}\sum _{n_1=0}^{N_1-1}\widehat{x}\left(n_1,n_2\right)W_{N_1}^{n_1{k}_1}{W}_{N_2}^{n_2{k}_2}=\sum _{n_2=0}^{N_2-1}\widehat{y}\left(k_1,n_2\right)W_{N_2}^{n_2{k}_2}$

[0426] If a two-dimensional DFT form, such as Equation 22, is used, the two-dimensional DFT can be decomposed into DFTs having a short length and operate. Accordingly, a computational load can be significantly reduced compared to an equivalent one-dimensional DFT.

[0427] According to Equations 13 and 14, the present disclosure performs a 3-point DFT of {circumflex over (x)}(0, n₂), {circumflex over (x)}(1, n₂), and {circumflex over (x)}(2, n₂) and a 5-point DFT of {circumflex over (x)}(0, n₂), {circumflex over (x)}(1, n₂), {circumflex over (x)}(2, n₂), {circumflex over (x)}(3, n₂), and {circumflex over (x)}(4, n₂) on a given n2.

[0428] The present disclosure may define a real part and imaginary part of ŷ(k₁, n₂) like Equation 23 with respect to ŷ(k₁, n₂) generated after the internal DFT loop of Equation 13, 14 is performed.

[0429] $\begin{array}{cc}\hat{y}\left(k_1,n_2\right)={\hat{y}}_R\left(k_1,n_2\right)+j·{\hat{y}}_1\left(k_1,n_2\right)& \left[\mathrm{Equation}23\right]\end{array}$

• • [0430] wherein ŷ_R indicates the real part, and ŷ₁ indicates the imaginary part.

[0431] Likewise, input {circumflex over (x)}(n₁, n₂) and output {circumflex over (X)}(k₁, k₂) may be decomposed into a real part and an imaginary part, respectively.

[0432] $\begin{array}{cc}\hat{x}\left(n_1,n_2\right)={\hat{x}}_R\left(n_1,n_2\right)+j·{\hat{x}}_1\left(n_1,n_2\right)& \left[\mathrm{Equation}24\right]\end{array}$ $\hat{X}\left(k_1,k_2\right)={\hat{X}}_R\left(k_1,k_2\right)+j·{\hat{X}}_I\left(k_1,k_2\right)$

• • [0433] wherein an input {circumflex over (x)}(n₁, n₂) may be pixels or residual data to which a designated transform is expected to be applied. Accordingly, actual {circumflex over (x)}(n₁, n₂) may be assumed to have a0 value.

[0434] Under such an assumption, the present disclosure may check relations between first transformed data ŷ(k₁, n₂) output by input symmetries imposed to a first step DFT (i.e., a 3-point DFT in the case of a 33-point DFT, and a 5-point DFT in the case of a 65-point DFT). Such symmetries are provided by the P and Q matrices of Equation 8 or 9, and are described in Equations 25 and 26.

[0435] $\begin{array}{cc}\mathrm{Case}1)x\left(0,n_2\right)=0,x\left(2,n_2\right)=-x\left(1,n_2\right)& \left[\mathrm{Equation}25\right]\end{array}$ $\mathrm{Case}2)x\left(0,n_2\right)=-x\left(0,n_2^{\prime }\right),x\left(1,n_2\right)=-x\left(2,n_2^{\prime }\right),x\left(2,n_2\right)=-x\left(1,n_2^{\prime }\right)$ $\mathrm{for}\mathrm{some}{n}_2^{\prime }$ $\begin{array}{cc}\mathrm{Case}1)x\left(0,n_2\right)=0,x\left(3,n_2\right)=-x\left(2,n_2\right),x\left(4,n_2\right)=-x\left(1,n_2\right)& \left[\mathrm{Equation}26\right]\end{array}$ $\mathrm{Case}2)x\left(0,n_2\right)=-x\left(0,n_2^{\prime }\right),x\left(1,n_2\right)=-x\left(4,n_2^{\prime }\right),x\left(2,n_2\right)=-x\left(3,n_2^{\prime }\right),x\left(3,n_2\right)=-x\left(2,n_2^{\prime }\right),x\left(4,n_2\right)=-x\left(1,n_2^{\prime }\right)$ $\mathrm{for}\mathrm{some}{n}_2^{\prime }$

[0436] Furthermore, in ŷ(k₁, n₂), first step output relations are the same as Equations 27 and 28.

[0437] $\begin{array}{cc}{\hat{y}}_R\left(2,n_2\right)={\hat{y}}_R\left(1,n_2\right)& \left[\mathrm{Equation}27\right]\end{array}$ ${\hat{y}}_I\left(0,n_2\right)=0,{\hat{y}}_I\left(2,n_2\right)=-{\hat{y}}_I\left(1,n_2\right)$ $\begin{array}{cc}{\hat{y}}_R\left(3,n_2\right)={\hat{y}}_R\left(2,n_2\right),{\hat{y}}_R\left(4,n_2\right)={\hat{y}}_R\left(1,n_2\right)& \left[\mathrm{Equation}28\right]\end{array}$ ${\hat{y}}_I\left(0,n_2\right)=0,{\hat{y}}_I\left(3,n_2\right)=-{\hat{y}}_I\left(2,n_2\right),{\hat{y}}_I\left(4,n_2\right)=-{\hat{y}}_I\left(1,n_2\right)$

[0438] Equations 25 and 27 indicate relations in a 3-point FFT belonging to a 33-point DFT. Equations 26 and 28 indicate relations in a 5-point FFT belonging to a 65-point DFT.

[0439] For example, in Equations 25 and 26, Case 1 occurs when n₂=0, and Case 2 occurs when n₂=11−n₂′, n₂′=1,2, . . . ,10 (n₂=13−n₂′, n₂′=1,2, . . . ,12). With respect to Case 1 inputs, real parts of all outputs from the 3-point FFT (5-point FFT) become 0. The present disclosure needs to maintain one (two) imaginary part outputs because the remaining one output (two outputs) can be recovered according to Equations 27 and 28.

[0440] In Equations 25 and 26, due to the input patterns of Case 2, the present disclosure has a relation between ŷ(k₁, n₂) and ŷ(k₁, n₂) as in Equation 29.

[0441] $\begin{array}{cc}{\hat{y}}_R\left(k_1,n_2\right)=-{\hat{y}}_R\left(k_1,n_2^{\prime }\right)& \left[\mathrm{Equation}29\right]\end{array}$ ${\hat{y}}_I\left(k_1,n_2\right)={\hat{y}}_I\left(k_1,n_2^{\prime }\right)$

[0442] In the case of Equation 29, relations between indices n₂=11−n₂′, n₂′=1,2, . . . ,10 (n₂=13−n₂′, n₂′=1,2, . . . ,12) of an 11-point FFT (13-point FFT) are also identically applied.

[0443] Accordingly, the present disclosure performs a 3-point FFT (5-point FFT) only when n₂ is in the range of [0, 5]([0, 6]) due to Equation 29, and thus can reduce an associated computational load.

[0444] Furthermore, in each 3-point FFT (5-point FFT) calculation in the range of [1, 5]([1, 6]), other parts of the outputs may be recovered according to Equation 21. Accordingly, only some outputs, that is, two (three) real part outputs and one (two) imaginary part output, are calculated.

[0445] Due to the symmetries present in the first step outputs (Equation 29), outputs calculated from the external loop (the second step FFT) in Equation 13, 14 are symmetrically arrayed. This can reduce a computational load. An input pattern of the external loop (the second step FFT) is the same as Equations 30 to 33.

[0446] $\begin{array}{cc}1)\mathrm{Real}\mathrm{part}{\hat{y}}_R\left(k_1,0\right)=0,{\hat{y}}_R\left(k_1,6\right)=-{\hat{y}}_R\left(k_1,5\right),{\hat{y}}_R\left(k_1,7\right)=-{\hat{y}}_R\left(k_1,4\right),& \left[\mathrm{Equation}30\right]\end{array}$ ${\hat{y}}_R\left(k_1,8\right)=-{\hat{y}}_R\left(k_1,3\right),{\hat{y}}_R\left(k_1,9\right)=-{\hat{y}}_R\left(k_1,2\right),{\hat{y}}_R\left(k_1,10\right)=-{\hat{y}}_R\left(k_1,1\right)$ $\begin{array}{cc}1)\mathrm{Real}\mathrm{part}{\hat{y}}_R\left(k_1,0\right)=0,{\hat{y}}_R\left(k_1,7\right)=-{\hat{y}}_R\left(k_1,6\right),{\hat{y}}_R\left(k_1,8\right)=-{\hat{y}}_R\left(k_1,5\right),{\hat{y}}_R\left(k_1,9\right)=-{\hat{y}}_R\left(k_1,4\right),& \left[\mathrm{Equation}31\right]\end{array}$ ${\hat{y}}_R\left(k_1,10\right)=-{\hat{y}}_R\left(k_1,3\right),{\hat{y}}_R\left(k_1,11\right)=-{\hat{y}}_R\left(k_1,2\right),{\hat{y}}_R\left(k_1,12\right)=-{\hat{y}}_R\left(k_1,1\right)$ $\begin{array}{cc}2)\mathrm{Imaginary}\mathrm{part}{\hat{y}}_I\left(k_1,6\right)={\hat{y}}_I\left(k_1,5\right),{\hat{y}}_I\left(k_1,7\right)={\hat{y}}_I\left(k_1,4\right),& \left[\mathrm{Equation}32\right]\end{array}$ ${\hat{y}}_I\left(k_1,8\right)={\hat{y}}_I\left(k_1,3\right),{\hat{y}}_I\left(k_1,9\right)={\hat{y}}_I\left(k_1,2\right),{\hat{y}}_I\left(k_1,10\right)={\hat{y}}_I\left(k_1,1\right)$ $\begin{array}{cc}2)\mathrm{Imaginary}\mathrm{part}{\hat{y}}_I\left(k_I,7\right)={\hat{y}}_I\left(k_1,6\right),{\hat{y}}_I\left(k_1,8\right)={\hat{y}}_I\left(k_1,5\right),{\hat{y}}_I\left(k_1,9\right)={\hat{y}}_I\left(k_1,4\right),& \left[\mathrm{Equation}33\right]\end{array}$ ${\hat{y}}_I\left(k_1,10\right)={\hat{y}}_I\left(k_1,3\right),{\hat{y}}_I\left(k_1,11\right)={\hat{y}}_I\left(k_1,2\right),{\hat{y}}_I\left(k_1,12\right)={\hat{y}}_I\left(k_1,1\right)$

[0447] Equation 30, 32 indicates input symmetries encountered in an 11-point FFT belonging to a 33-point FFT.

[0448] Equation 31, 33 indicates input symmetries encountered in a 13-point FF belonging to a 65-point FFT. According to an external loop iteration, other symmetries are also encountered among input sets of an 11-point FFT (13-point FFT). This enables output recovering for iteration from one of previous iterations.

[0449] In the present disclosure, if the vector of ŷ(k₁, n₂) is represented as Ŷ(k₁)=[_y(k₁, 0) ŷ(k₁, 1) . . . ŷ(k₁, N₂−1)]^T=Ŷ_R(k₁)+j·Ŷ_I(k₁), input symmetries present in an iteration process may be represented like Equation 34:

[0450] $\begin{array}{cc}\mathrm{Case}1\text{:}{\hat{Y}}_I\left(k_1\right)=0& \left[\mathrm{Equation}34\right]\end{array}$ $\mathrm{Case}2\text{:}{\hat{Y}}_R\left(k_1\right)={\hat{Y}}_R\left(k_1^{\prime }\right),{\hat{Y}}_I\left(k_1\right)=-{\hat{Y}}_I\left(k_1^{\prime }\right)$

[0451] In a two-dimensional DFT such as a 33-point FFT (65-point FFT), k1 has a range of [0, 2]([0, 4]).

[0452] In Equation 34, Case 1 occurs only when k₁=0. In Equation 34, Case 2 occurs only when k₁=3−k₁′, k₁′=1,2 (k₁ '₂ 5−k₁′, k₁′=1,2,3,4).

[0453] From the symmetries in Equation 34, the output of a skipped iteration may be derived from one of previous iterations thereof. Accordingly, the number of valid iterations of an 11-point FFT (15-point FFT) in a 33-point FFT (65-point FFT) can be reduced from 3(5) to 2(3).

[0454] Furthermore, according to Equations 8 and 9, the present disclosure may take only the imaginary parts of outputs from a 33-point FFT (65-point FFT). Accordingly, in Equation 34, output patterns of respective cases may be represented like Equations 35 to 38.

[0455] $\begin{array}{cc}\mathrm{Case}1\text{:}{\hat{X}}_I\left(k_1,0\right)=0,{\hat{X}}_I\left(k_1,11-k_2\right)=-{\hat{X}}_I\left(k_1,k_2\right),k_2=1,2,\dots ,10& \left[\mathrm{Equation}35\right]\end{array}$ $\begin{array}{cc}\mathrm{Case}1\text{:}{\hat{X}}_I\left(k_1,0\right)=0,{\hat{X}}_I\left(k_1,13-k_2\right)=-{\hat{X}}_I\left(k_1,k_2\right),k_2=1,2,\dots ,12& \left[\mathrm{Equation}36\right]\end{array}$ $\begin{array}{cc}\mathrm{Case}2\text{:}{\hat{X}}_I\left(k_1,0\right)=-{\hat{X}}_I\left(3-k_1,0\right),{\hat{X}}_I\left(k_1,k_2\right)=-{\hat{X}}_I\left(3-k_1,11-k_2\right),k_1=1,2,k_2=1,2,\dots ,10& \left[\mathrm{Equation}37\right]\end{array}$ $\begin{array}{cc}\mathrm{Case}2\text{:}{\hat{X}}_I\left(k_1,0\right)=-{\hat{X}}_I\left(5-k_1,0\right),{\overline{X}}_I\left(k_1,k_2\right)=-{\hat{X}}_I\left(5-k_1,13-k_2\right),k_1=1,2,3,4,k_2=1,2,\dots ,12& \left[\mathrm{Equation}38\right]\end{array}$