Patent Publication Number: US-2022224947-A1

Title: Coding method and related device

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of International Patent Application No. PCT/CN2020/102694, filed on Jul. 17, 2020, which claims priority to Chinese Patent Application No. 201910768348.8, filed on Aug. 15, 2019. The disclosures of the aforementioned applications are hereby incorporated by reference in their entireties. 
    
    
     TECHNICAL FIELD 
     This application relates to the image processing field, and in particular, to a coding method and a related device. 
     BACKGROUND 
     Entropy coding is a coding technology widely used in image and video data compression, essence of the entropy coding is a lossless data compression scheme that is independent of specific characteristics of a medium, and no information is lost according to Shannon&#39;s entropy theorem. Common entropy coding includes Shannon coding, Huffman coding, arithmetic coding, and the like. The entropy coding aims to losslessly describe a source symbol with a code length as short as possible. At present, entropy coding is widely used in fields such as image and video compression fields, and plays a quite important role in reducing occupied storage space and improving data transmission efficiency. However, a variable-length coding scheme used in the conventional technology has a relatively low throughput and low coding efficiency. 
     SUMMARY 
     Embodiments of this application provide a coding method and a related device, to increase a compression throughput of a polar code and implement fast lossless compression of parallel polar coding. 
     According to a first aspect, an embodiment of this application provides a coding method. The method includes: obtaining a plurality of pieces of run-length encoding (RLE) data and distribution probabilities corresponding to the plurality of pieces of RLE data; sorting the plurality of pieces of RLE data based on the distribution probabilities, and mapping the plurality of pieces of sorted RLE data onto a plurality of pieces of reassembled data; expanding the plurality of pieces of reassembled data into a plurality of pieces of binary data, generating a first matrix, and calculating an occurrence probability of a bit 1 in each column in the first matrix based on the distribution probabilities; determining, based on the occurrence probability, a code sequence obtained by processing a source signal, where the code sequence includes a first set and a second set, the first set is a bit reserved after compression, and the second set is a bit discarded after compression; and finally decoding a first vector to output a third set, where the first vector is an all-0 sequence, or is a vector obtained by multiplying a vector corresponding to the first set and a polarization matrix, and the third set includes the bit reserved after compression and a location at which a decoding error occurs in the bit discarded after compression. Color transform, grayscale translation, discrete cosine transform (DCT) transform, data quantization, zig-zag scanning, and run-length encoding are performed on image data to obtain RLE data, the RLE data is reassembled, reassembled RLE data is converted into a multi-bit binary bit sequence, and finally a polar code is designed to perform parallel compression on a signal of each bit plane. This increases a compression throughput of the polar code and implements fast lossless compression of parallel polar coding. 
     In a possible design, the first set is a bit whose polarized entropy approximates to 1 in the code sequence, and the second set is a bit whose polarized entropy approximates to 0 in the code sequence. 
     In another possible design, the polarized entropy is determined based on the occurrence probability. 
     In another possible design, the decoding a first vector to output a third set includes: performing decoding based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =0 N , U F =U S , Y N  is a received signal of the polar decoder, U F  is the fixed bit set, U S  is the first set, and N is an integer greater than or equal to 1. A design of a lossless compression polar code is equivalent to a design of polar channel decoding for a binary symmetric channel. This implement fast lossless compression of the polar code. 
     In another possible design, the decoding a first vector to output a third set includes: performing decoding based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =[U F , 0 I ]*G N , U F =0 F , Y N  is a received signal of the polar decoder, U F  is the fixed bit set, G N  is the polarization matrix, and N is an integer greater than or equal to 1. A matrix corresponding to the fixed bit set is translated, so that the existing polar decoder is directly used. This implements fast lossless compression of parallel polar coding. 
     In another possible design, the decoding a first vector to output a third set includes: when the estimated value is different from an original value of the bit discarded after compression, flipping the estimated value, and recording the location at which a decoding error occurs in the bit discarded after compression. 
     In another possible design, the plurality of pieces of RLE data are sorted in descending order of the distribution probabilities; and then the plurality of pieces of sorted RLE data are mapped onto the plurality of pieces of reassembled data. For example, RLE data with a highest distribution probability is mapped onto 0, RLE data with a second highest probability is mapped onto 1, a third highest probability is mapped onto 2, and so on. Through data reassembly, a correlation between bits is reduced, and compression performance is improved. 
     In another possible design, layering is performed based on each column of the first matrix to obtain a plurality of bit planes, and the occurrence probability of 1 in each bit plane is calculated, to implement parallel layered compression of polar coding. 
     According to a second aspect, an embodiment of this application provides a coding apparatus. The coding apparatus is configured to implement the method and the function in the first aspect, and is implemented by hardware/software. The hardware/software of the coding apparatus includes a module corresponding to the foregoing function. 
     According to a third aspect, an embodiment of this application provides a network element device, including a processor, a memory, and a communications bus. The communications bus is configured to implement connection and communication between the processor and the memory, and the processor executes a program stored in the memory, to implement the steps in the first aspect. 
     In a possible design, a network element device provided in this application may include a corresponding module configured to perform behaviors of the network element device in the foregoing method design. The module may be software and/or hardware. 
     According to a fourth aspect, this application provides a computer-readable storage medium. The computer-readable storage medium stores instructions. When the instructions are run on a computer, the computer is enabled to perform the method in the first aspect. 
     According to a fifth aspect, this application provides a computer program product including instructions. When the computer program product runs on a computer, the computer is enabled to perform the method in the first aspect. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
       To describe technical solutions in embodiments of this application or in the background more clearly, the following describes the accompanying drawings required for describing the embodiments of this application or the background. 
         FIG. 1  is a schematic flowchart of a typical JPEG compression algorithm according to an embodiment of this application; 
         FIG. 2  is a schematic diagram of a quantization matrix used in a JPEG compression algorithm according to an embodiment of this application; 
         FIG. 3  is a schematic diagram of a quantized frequency component according to an embodiment of this application; 
         FIG. 4  is a schematic diagram of Huffman coding according to an embodiment of this application; 
         FIG. 5  is a schematic diagram of a statistical probability distribution according to an embodiment of this application; 
         FIG. 6  is a schematic diagram of an architecture of a coding system according to an embodiment of this application; 
         FIG. 7  is a schematic flowchart of a coding method according to an embodiment of this application; 
         FIG. 8  is a schematic diagram of RLE data reassembly according to an embodiment of this application; 
         FIG. 9  is a schematic diagram of a distribution comparison before and after data reassembly according to an embodiment of this application; 
         FIG. 10  is a schematic diagram of polar-code source polarization according to an embodiment of this application; 
         FIG. 11  is an equivalent schematic diagram of polar-code source compression and channel communication according to an embodiment of this application; 
         FIG. 12  is a schematic diagram of a BSC channel according to an embodiment of this application; 
         FIG. 13  is a schematic flowchart of lossless polar compression according to an embodiment of this application; 
         FIG. 14  is a schematic diagram of a coding apparatus according to an embodiment of this application; and 
         FIG. 15  is a schematic diagram of a structure of a network element device according to an embodiment of this application. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     The following describes the embodiments of this application with reference to the accompanying drawings in the embodiments of this application. 
       FIG. 1  is a schematic flowchart of a typical JPEG compression algorithm according to an embodiment of this application. For example, for Joint Photographic Experts Group (JPEG) image compression coding, color transform is first performed on an original image to obtain three grayscale matrices, that is, Y, U and V, and a grayscale range of each of the grayscale matrices is adjusted by using a corresponding level offset; then, discrete cosine transform (DCT) is performed on shifted grayscale matrices as per 8×8 small matrix blocks (0 is padded if necessary), to obtain component information of discrete frequencies; and next, quantization (uniform scalar quantization) is performed on the component information of the discrete frequencies to obtain a direct current coefficient (DC coefficient) and an alternating current coefficient (AC coefficient).  FIG. 2  is a schematic diagram of a quantization matrix used in a JPEG compression algorithm according to an embodiment of this application. The direct current coefficient may be encoded through differential pulse code modulation (DPCM), and then variable-length coding is performed on data obtained through DPCM encoding, to obtain a DC bitstream. In contrast, for the alternating current coefficient, because an image signal mainly includes low-frequency components, and a human eye is more sensitive to a low-frequency component, a quantization step for quantizing the AC part is usually larger. This leads to a plurality of 0s in signals of the AC part. 
       FIG. 3  is a schematic diagram of a quantized frequency component according to an embodiment of this application. The alternating current coefficient is quantized, and an 8×8 matrix is converted into a sequence string through zig-zag scanning, where the sequence string is (15, 0, −2, −1, −1, −1, 0, . . . ). A trailer of the sequence string includes a plurality of consecutive 0s. To reduce occupied space, run-length encoding (RLE) may be performed on the sequence string to obtain a shorter sequence string. Specifically, an operation is performed on a digital sequence string including many consecutive 0s, and any non-0 digit a in the sequence string is encoded as two digits (N, a). N represents a quantity of consecutive 0s before a location of a digit a. For example, a sequence string (0, 0, 8, 0, 5, 5, 0, 0, 0, 6) is encoded as {(2, 8), (1, 5), (0, 5), (3, 6)}; and a sequence string (9, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 1) is encoded as ((0, 9), (4, 4), (5, 1)). After the run-length encoding data is obtained, because probabilities of these pieces of data are different, entropy coding needs to be performed on these pieces of data to remove redundancy. Huffman coding or arithmetic coding is usually used in a system. Huffman coding is used as an example in this embodiment of this application. 
     For conventional entropy coding schemes such as Huffman coding, run-length encoding data is considered as being independently generated from a single source based on a specific distribution. Therefore, before Huffman coding is performed, distribution probabilities of all data need to be calculated, and a corresponding dictionary needs to be generated based on the distribution probabilities by using Huffman coding. A basic principle is that a numeral with a higher distribution probability is represented by shorter binary bits, and a numeral with a lower distribution probability is represented by longer binary bits.  FIG. 4  is a schematic diagram of Huffman coding according to an embodiment of this application. At a second layer, a distribution probability of a is 45%, which is greater than a distribution probability of any other piece of data, and a is encoded by using one bit, that is, represented by 0. At a fourth layer, three bits are used for coding, where b=101, c=100, and d=111. At a fifth layer, a distribution probability of f is 5% and a distribution probability of e is 9%, which are both less than distribution probabilities of other data, and f and e are encoded by using four bits, where e=1101 and f=1100. After the foregoing Huffman coding is completed, a JPEG image compression process ends. 
     According to the foregoing description of the run-length encoding and the entropy coding, a string of digit pairs {(N 1 , a 1 ), (N 2 , a 2 ), (N 3 , a 3 ), (N 4 , a 4 ), . . . , (N i , a i ), . . . } is obtained through run-length encoding, where N 1  represents a quantity of consecutive 0s before a digit a i . In entropy coding, the quantity of 0s before the digital symbol a i  that is obtained through run-length encoding is considered as signals generated from one discrete source based on a fixed distribution, and then statistics collection and compression are performed on a signal. For example,  FIG. 5  is a schematic diagram of a statistical probability distribution obtained through Huffman coding according to an embodiment of this application. N={0, 1, 2} (that is, a value of N i  is 0, 1, or 2), a=(0, 1, 2, 4, 5, 6, 7), and calculated occurrence frequencies of {0, 1, 2, 4, 5, 6, 7} are {0.3, 0.15, 0.05, 0.1, 0.20, 0.05, 0.15}, respectively. A dictionary obtained through Huffman coding is [00, 011, 1111, 110, 10, 1110, 010] that represents {0, 1, 2, 4, 5, 6, 7}, respectively. An average compression length implemented is 2.6 bits. Probabilities corresponding to the digits are {0.3, 0.15, 0.05, 0.1, 0.20, 0.05, 0.15}, and entropy is 2.5710. Through Huffman coding, optimal performance is nearly achieved. 
     The Huffman-based entropy coding is a type of variable-length coding in source compression. Because a code structure similar to a binary tree is used, and a Huffman code is a typical prefix code, that is, any code word in a codebook is not a prefix part of other code words, the Huffman-based entropy coding is a codebook mapping mode in which unique restoration can be performed without setting breakpoints. However, Huffman decoding also has a disadvantage, that is, breakpoints need to be found one by one based on the codebook in a code dictionary and a decision needs to be made. For example, as shown in  FIG. 5 , Huffman decoding needs to be performed on a binary sequence 000111111110101110010. The 1 st  received symbol 0 is first searched for, but does not exist in a code dictionary [00, 011, 1111, 110, 10, 1110, 010]; “00” continues to be searched for, and if a corresponding symbol is found in the dictionary, “00” is decoded as 0; a next “0” is searched for but there is no corresponding codebook, and “01” is then searched for but there is still no corresponding codebook; and then “011” is searched for, and if a corresponding symbol is found in the dictionary, “011” is decoded as 1. This process is repeated until all characters are restored. 
     It can be learnt that the variable-length coding has the following advantage: A symbol with a higher probability can be represented by a short code and a symbol with a lower probability can be represented by a long code, to achieve an average length, and gradually achieve optimal compression efficiency. However, bits need to be compared and searched for one by one during decoding, resulting in a relatively low throughput rate and low coding efficiency. To resolve the foregoing technical problems, the embodiments of this application provide the following solutions. 
       FIG. 6  is a schematic diagram of an architecture of a coding system according to an embodiment of this application. JPEG operations such as color transform, grayscale translation, 8×8 DCT transform, data quantization, zig-zag scanning, and run-length encoding (RLE) are first performed on image data to obtain a plurality of pieces of RLE data. Then, the RLE data is sorted in descending order of probabilities to obtain a symbol set {a_1, a_2, . . . , a_n}, and the corresponding probabilities of {a_1, a_2, . . . , a_n} are {p_1, p_2, . . . , p_n} that satisfies a relationship p_1≥p_2≥ . . . ≥p_n. (a_1, a_2, . . . , a_n) is respectively mapped onto {0, 1, . . . , n−1} to complete data reassembly, and then reassembled data is expanded in binary natural order. For example, when n=4, if data obtained after sorting the RLE data is (‘255’, ‘55’, ‘72’, ‘12’), {‘255’, ‘55’, ‘72’, ‘12’} is mapped onto corresponding {0, 1, 2, 3}, and the mapped values are represented by a corresponding binary sequence {00000000, 00000001, 00000010, 00000011}. Occurrence probabilities of 0 and 1 at each layer (column) of the foregoing binary sequence (eight layers herein) are calculated, and parallel layered compression of polar coding is completed based on the occurrence probabilities. After each layer of compression is completed, data splicing is performed on compressed data at each layer to complete a compression process. It should be noted that an operation process of a receive end is an inverse process of the foregoing process, and details are not described herein. A specific coding process is as follows. 
     Fixed-length coding is used in this embodiment of this application. The fixed-length coding is a type of linear coding, in which a high-dimensional redundant source vector with a fixed length (which is assumed to be N) is compressed into a vector whose dimension is approximately NH(X), where H(X) is entropy of a source X. If X is a binary signal including 0 and 1, H(X)=−p log 2  p−(1−p) log 2 (1−p), where p is a probability that X is equal to 1. When the fixed-length coding is used, N symbols are simultaneously processed each time, and during decoding, RN compressed bits are extracted based on a fixed compression rate R to restore N original symbols (where R≥H(X)). In this case, the system has a relatively large throughput and is relatively stable, and a linear channel coding technology can be used. In this embodiment of this application, extension of a polar code in source compression is used, so that entropy coding is implemented when an existing polar code channel decoder is used in source compression, thereby improving entropy coding efficiency. 
       FIG. 7  is a schematic flowchart of a coding method according to an embodiment of this application. Steps in this embodiment of this application include at least the following steps. 
     S 701 : Obtain a plurality of pieces of run-length encoding (RLE) data and distribution probabilities corresponding to the plurality of pieces of RLE data. Color transform, grayscale translation, 8×8 DCT transform, data quantization, zig-zag scanning, and run-length encoding may be performed on an original image to obtain a plurality of pieces of RLE data. For a specific method thereof, refer to the foregoing process. A dynamic range of the RLE data may be 0-255, and a distribution probability of each of 256 characters may be obtained by counting a quantity of occurrences of the character. 
     S 702 : Sort the plurality of pieces of RLE data based on the distribution probabilities, and map the plurality of pieces of sorted RLE data onto a plurality of pieces of reassembled data. 
     During specific implementation, the plurality of pieces of RLE data may be sorted in descending order of the distribution probabilities. Then, the plurality of pieces of sorted RLE data are mapped. 
       FIG. 8  is a schematic diagram of RLE data reassembly according to an embodiment of this application. A string of digit pairs ((N 1 , a 1 ), (N 2 , a 2 ), (N 3 , a 3 ), (N 4 , a 4 ), . . . , (N i , a i ), . . . ) is obtained through run-length encoding, where N i  represents a quantity of consecutive 0s before a digit a i . N={0, 1, 2} (that is, a value of N i  is 0, 1, or 2), and a represents a value of a non-0 element. The digit pairs are mapped onto a={0, 1, 2, 4, 5, 6, 7}, and calculated occurrence frequencies of {0, 1, 2, 4, 5, 6, 7} are {0.3, 0.15, 0.05, 0.1, 0.20, 0.05, 0.15}, respectively. Based on this, calculated discrete entropy of a source is 2.5710. During data reassembly, a probability set {0.30, 0.20, 0.15, 0.15, 0.1, 0.05, 0.05} in a right figure is obtained by sorting the distribution probabilities in descending order, and characters of {0.3, 0.2, 0.15, 0.15, 0.1, 0.05, 0.05} are listed from 0 to 6. In this case, a mapping relationship resulting from the reassembly is 0-&gt;0, 1-&gt;2, 2-&gt;5, 4-&gt;4, 5-&gt;1, 6-&gt;6, and 7-&gt;3. 
     S 703 : Expand the plurality of pieces of reassembled data into a plurality of pieces of binary data, generate a first matrix, and calculate an occurrence probability of a bit 1 in each column in the first matrix based on the distribution probabilities. 
     Because a binary polar code is used for compression, a plurality of pieces of reassembled data need to be represented by binary bits, and binary natural sequence expansion is performed on decimal numbers, that is, the plurality of pieces of reassembled data, ranging from 0 to 255, that is, a decimal number B is represented by a series B=Σ i=0   7 b i · 2   b     i   , where b i =0, 1. B may be uniquely represented by a sequence b 7 b 6 b 5 b 4 b 3 b 2 b 1 b 0 , where b 0  is a least significant bit (LSB), and b 7  is a most significant bit (MSB). After the plurality of pieces of reassembled data are expanded into a plurality of pieces of binary data, a first matrix may be generated, where each row of data in the first matrix is corresponding to one piece of binary data. Layering may be performed based on each column of the first matrix to obtain a plurality of bit planes, the occurrence probability of 1 in each bit plane is calculated, and parallel layered compression of polar coding is completed based on the occurrence probabilities. 
     For example, as shown in  FIG. 8 , calculated occurrence frequencies of the plurality of pieces of RLE data, that is, a={0, 1, 2, 4, 5, 6, 7}, are {0.3, 0.15, 0.05, 0.1, 0.20, 0.05, 0.15}, respectively. The plurality of pieces of RLE data are mapped onto the plurality of pieces of reassembled data: 0-&gt;0, 1-&gt;2, 2-&gt;5, 4-&gt;4, 5-&gt;1, 6-&gt;6, and 7-&gt;3, and then the plurality of pieces of reassembled data are expanded into binary data. To be specific, {0, 1, 2, 3, 4, 5, 6} is represented by {‘000’, ‘001’, ‘010’, ‘011’, ‘100’, ‘101’, ‘110’} and is respectively corresponding to the distribution probabilities (0.30, 0.20, 0.15, 0.15, 0.1, 0.05, 0.05), and the generated first matrix is 
     
       
         
           
             
               [ 
               
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     1 
                   
                   
                     1 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     0 
                   
                   
                     1 
                   
                 
                 
                   
                     1 
                   
                   
                     1 
                   
                   
                     0 
                   
                 
               
               ] 
             
               
           
         
       
     
     Then, the occurrence probability of a bit 1 in each column is calculated. The last three bits in the first column are 1, and an occurrence probability is 0.1+0.05+0.05=0.2; the third, fourth, and seventh bits in the second column are 1, and an occurrence probability is 0.15+0.15+0.05=0.35; and the second, fourth, and sixth bits in the third column are 1, and an occurrence probability is 0.2+0.15+0.05=0.4. In this case, the occurrence probabilities of a bit 1 in all the columns are {0.200, 0.3500, 0.400}. Each column can be considered as being obtained by generating 1 based on q i  and generating 0 based on (1−q i ) by using a Bernoulli source. The source is denoted as Ber(q i ) for short. 
     To implement independent parallel compression, the b i  sequence is directly compressed by without considering a correlation between b i . In this case, independent entropy of each bit may be expressed as H(b i )=−q i  log 2  q i −(1−q i ) log 2 (1−q i ), where q i  is a probability that b i  is equal to 1. In this case, compression performance is a sum of independent entropy of 8 bits, that is i i=0   7  H(b i ). According to a chain rule of entropy, the following relationship may be obtained: 
         H ( P )= H ( b   7   b   6   b   5   b   4   b   3   b   2   b   1   b   0 )=Σ i=0   7   H ( b   i   |b   i-1   b   i-2   . . . b   0 )≤Σ i=0   7   H ( b   i )
 
     If bits are not correlated with each other, H(b i |b i-1 b i-2  . . . b 0 )=H(b i ) holds true. It can be learnt that an effect of independent parallel compression is always worse than that of joint compression. To minimize a performance loss, the correlation between b i  is expected to be as small as possible, and therefore the plurality of pieces of RLE data need to be reassembled. 
       FIG. 9  is a schematic diagram of a distribution comparison before and after data reassembly according to an embodiment of this application. As shown in a left figure of  FIG. 9 , a dynamic range of RLE data is 0-255, and a distribution probability of each of 256 characters may be obtained by counting a quantity of occurrences of the character. If reassembly and mapping are not performed on the plurality of pieces of RLE data, and binary natural number expansion is performed on the RLE data, that is, RLE data 0 is represented by ‘00000000’, RLE data 1 is represented by ‘00000001’, and so on, the obtained distribution correlation between b i  is quite high. Σ i=0   7  H(b i )=6.22 is obtained through calculation in the left figure, but actually H(P)=4.10, and in this case, there are two bits of redundancy. As shown in a right figure of  FIG. 9 , because sorting is performed in descending order of distribution probabilities, RLE data with a highest distribution probability is mapped onto 0, RLE data with a second highest distribution probability is mapped onto 1, and so on. RLE data with a higher distribution probability after the reassembly is distributed before RLE data with a lower distribution probability after the reassembly. After the reassembly and mapping are completed, binary expansion is finally performed on the plurality of pieces of reassembled data, to obtain independent entropy i i=0   7  H(b i )=4.36 that is only 0.26 greater than the original H(P). Therefore, a performance loss is greatly reduced through data reassembly. 
     S 704 : Determine, based on the occurrence probability, a code sequence obtained by processing a source signal, where the code sequence includes a first set and a second set, the first set is a bit reserved after compression, and the second set is a bit discarded after compression. 
     The first set is a bit whose polarized entropy approximates to 1 in the code sequence, and the second set is a bit whose polarized entropy approximates to 0 in the code sequence. Further, the polarized entropy is determined based on the occurrence probability. 
       FIG. 10  is a schematic diagram of polar-code source polarization according to an embodiment of this application. It is assumed that X 1  and X 2  are two independent Ber(q) sources, where source entropy of Ber(q) sources is H(X 1 )=H(X 2 )=H(q)=−q log 2  q−(1−q) log 2 (1−q). Relationships U 1 =X 1 ⊖X 2  and U 2 =X 2  are obtained by using a polarization matrix 
     
       
         
           
             
               [ 
               
                 
                   
                     1 
                   
                   
                     0 
                   
                 
                 
                   
                     1 
                   
                   
                     1 
                   
                 
               
               ] 
             
             . 
           
         
       
     
     Because the polarization matrix is an invertible matrix, a sum of entropy after the polarization operation remains unchanged, that is, 
         H ( X   1   X   2 )= H ( U   1   U   2 )= H ( U   1 )+ H ( U   2   |U   1 ) 
     Because U 2 =X 2 , H(U 2 |U 1 )≤H(X 2 )=H(X 1 ). The sum of the entropy remains unchanged, and therefore H(U 1 )≥H(X 1 ). It can be learnt that after the polarization operation is performed, the two independent and identically distributed Bernoulli sources become a source with greater source entropy and a source with smaller source entropy. This is a basic principle of source polarization. 
     If the foregoing process is repeated, the source entropy, that is, (H(U 1 ) and H(U 2 |U 1 )), of the two independent and identically distributed sources is polarized in a next step, the source entropy may further be polarized. The polarization matrix in this case is 
     
       
         
           
             
               
                 G 
                 N 
               
               = 
               
                 
                   [ 
                   
                     
                       
                         1 
                       
                       
                         0 
                       
                     
                     
                       
                         1 
                       
                       
                         1 
                       
                     
                   
                   ] 
                 
                 
                   ⊗ 
                   n 
                 
               
             
             , 
           
         
       
     
     ⊗ is a tensor product, and the polarization process is implemented by using U N =X N ×G N . 
     According to the chain rule of entropy H(U N )=Σ i=1   N H(U i |U 1   i-1 ). Then, according to a source polarization theory, H(U i |U 1   i-1 ) is continually polarized with an increase of N but falls within a range 0≤H(U i |U 1   i-1 )≤1. When N→∞ in a limit case, H(U i |U 1   i-1 ) is polarized to 1 or 0. Because of total entropy conservation, the following equation holds true: 
         H ( U   N )= H ( X   N )= NH ( X ) 
     A proportion H(X) of parts that are 1 to polarized H(U i |U 1   i-1 ) may be obtained, namely, 
     
       
         
           
             
               
                 lim 
                 
                   N 
                   → 
                   ∞ 
                 
               
               ⁢ 
               
                 
                   
                     
                       | 
                       
                         i 
                         ∈ 
                         
                           [ 
                           N 
                           ] 
                         
                       
                     
                     : 
                     
                       H 
                       ⁡ 
                       
                         ( 
                         
                           
                             U 
                             i 
                           
                           | 
                           
                             U 
                             1 
                             
                               i 
                               - 
                               1 
                             
                           
                         
                         ) 
                       
                     
                   
                   = 
                   
                     1 
                     | 
                   
                 
                 N 
               
             
             = 
             
               
                 
                   H 
                   ⁡ 
                   
                     ( 
                     X 
                     ) 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 and 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     lim 
                     
                       N 
                       → 
                       ∞ 
                     
                   
                   ⁢ 
                   
                     
                       
                         
                           | 
                           
                             i 
                             ∈ 
                             
                               [ 
                               N 
                               ] 
                             
                           
                         
                         : 
                         
                           H 
                           ⁡ 
                           
                             ( 
                             
                               
                                 U 
                                 i 
                               
                               | 
                               
                                 U 
                                 1 
                                 
                                   i 
                                   - 
                                   1 
                                 
                               
                             
                             ) 
                           
                         
                       
                       = 
                       
                         1 
                         | 
                       
                     
                     N 
                   
                 
               
               = 
               
                 1 
                 - 
                 
                   
                     H 
                     ⁡ 
                     
                       ( 
                       X 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     In this way, compression of an X N  signal can be converted to compression of U N . Because H(U i |U 1   i-1 )=0, some bits in U N  may be entirely determined by other bits U 1   i-1  and may be discarded after compression. In this case, only the part H(U i |U 1   i-1 )=1 needs to be saved. A set is set to S={i∈[N]: H(U i |U 1   i-1 )→1}. A U sequence corresponding to the set is U S , a complementary set of S is S c , and in this case, [U S , U S     c   ]=U N . 
     S 705 : Decode a first vector to output a third set, where the first vector is an all-0 sequence, or is a vector obtained by multiplying a vector corresponding to the first set and a polarization matrix, and the third set includes the bit reserved after compression and a location at which a decoding error occurs in the bit discarded after compression. 
     During specific implementation, decoding is performed based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =0 N , U F =U S , Y N  is a received signal of the polar decoder, that is, the first vector, U F  is the fixed bit set, U S  is the first set, and N is an integer greater than or equal to 1. Alternatively, decoding is performed based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =[U F , 0 I ]*G N , U F =0 F , Y N  is a received signal of the polar decoder, that is, the first vector, G N  is the polarization matrix, U F  is the fixed bit set, and N is an integer greater than or equal to 1. 
     Then, decoding may be performed to obtain the estimated value of the bit discarded after compression. When the estimated value is different from an original value of the bit discarded after compression, the estimated value is flipped, and the location at which a decoding error occurs in the bit discarded after compression is recorded. When the estimated value is equal to an original value of the bit discarded after compression, a next bit is decoded and checked. Data splicing is finally performed to complete a compression process. 
     Because H(U i |U 1   i-1 ) corresponding to bits in U S     c    approximates to 0, most of U i  in U S     c    can be obtained based on U 1   i-1 . An estimated value Û i  of U i  may be derived from U 1   i-1  by using a principle similar to polar code decoding. If IT; is inconsistent with U i , a location i needs to be recorded; otherwise, the location i does not need to be recorded. It is assumed that a polar code SC (successive cancellation) decoder is used to restore U S     c    from U S . Because N is a finite value, source polarization is incomplete, and there is a specific possibility of a decoding error. An error location is defined as T: {i∈S c : Û i   SC ≠U i }, and Û i   SC  represents the estimated value U i  obtained through SC decoding. Obviously, when N→∞, a value proportion of the set T is |T|/N→0, and therefore a polar code achieves an optimal compression length H(X). Same as coding, lossless compression decoding uses an SC polar decoder to restore U S     c    from U S . Because the decoding error location is known, the decoding result Û i   SC  corresponding to i in T may be flipped to obtain the correct U i . In this way, U N  can be fully restored, thereby implementing lossless compression. 
       FIG. 11  is an equivalent schematic diagram of polar-code source compression and channel communication according to an embodiment of this application. A design of a lossless compression polar code for a Ber(q) source may be equivalent to a design of polar channel coding for a binary symmetric channel (BSC) (q). 
       FIG. 12  is a schematic diagram of a BSC channel according to an embodiment of this application. An error probability of the BSC channel is ϵ. The channel parameter ϵ is set to be the same as a Bernoulli source parameter, that is, ϵ=q. A channel capacity of BSC(q) may be calculated, that is, 1−H(q)=1+q log 2  q+(1−q) log 2 (1−q), and is exactly complementary to H(q). Specifically, a channel is set to W=BSC(q), n=log 2  N, and N polarized channels resulting from n times of polarization are represented by {i∈[N], W N   (i) )}. It can be theoretically proved that capacities of these polarized channels are complementary to the polarized source entropy, that is, I(W N   (i) )=1−H(U i |U 1   i-1 ). A specific proof process is not described. 
     According to the channel polarization coding theory, a subchannel obtained through polarization is used to place an information bit, and a remaining subchannel is used to place a fixed bit. Then, an information bit set is defined as I={i∈[N]: I(W N   (i) )→1} and a fixed bit set is defined as F=I c . According to the foregoing complementary relationship, equivalent correspondences, that is, U F  ↔U S  and U I ↔U S     c   , may be obtained. Proportion relationships of the two parts are 
     
       
         
           
             
               
                 | 
                 
                   U 
                   S 
                 
                 | 
               
               N 
             
             → 
             
               
                 
                   H 
                   ⁡ 
                   
                     ( 
                     q 
                     ) 
                   
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 and 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     | 
                     
                       U 
                       I 
                     
                     | 
                   
                   N 
                 
               
               → 
               
                 1 
                 - 
                 
                   
                     H 
                     ⁡ 
                     
                       ( 
                       q 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     Therefore, polar code construction sorting during source compression may be completely equivalent to a coding design for the BSC channel. 
     Polar code channel decoding may be used in a calculation process of source coding. Specifically, during source compression, whether the complementary set U S     c    can be successfully decoded is checked when U S  is given, and an error location is recorded if the error location exists, to implement lossless restoration. The polar code channel decoding process is a process of decoding U I  based on the channel received signal Y N  and the fixed bit set U F . A typical polar code SC decoder, BP (belief propagation) decoder, and SCL (successive cancellation list) decoder can all implement the foregoing functions. 
     A difference between the correspondences, that is, U F  ↔U S  and U I  ↔U S     c   , lies in that during polar channel encoding, U F  is usually set to all 0s, while a value of U S  during source compression is entirely determined by an output of the source X N . In addition, during source compression, actually there is no channel output signal Y N , and therefore a virtual channel output needs to be abstracted. For a channel model of BSC(q), a relationship between the input X and the output Y is Y=X ⊕Z, where ⊕ is a modulo 2 operation, Z is noise independent of X, and a probability that a value of Z is 1 is q, which is exactly a Bernoulli source Ber(q). If X is used as a source Ber(q) same as Z, that is, Y=0 is output, decoding of X is actually equivalent to restoration of the source Ber(q). 
     In conclusion, a BSC channel may be first abstracted, and noise of the BSC channel is completely identical to X N , to obtain Y N =0 N . A polar decoder may be used to correctly restore U I  based on Y N  and U F , and U F  may be set as a specific value of U S . In this way, U I =U S     c    can be implemented. For example, an SC decoder is used, and f SC (−) is set to a polar code SC decoding function. In this case, Û S     c   =Û I =f SC (Y N =0 N , U F =U S ). U F  can be translated to include all 0s through linear transformation. In this way, an existing polar decoder can be directly used. Specifically, 
         Y   N   =X   N   ⊕Z   N =0 N    
         U   N   G   N   ⊕Z   N   =Y   N =0 N    
       [ U   F   ,U   I ] G   N   ⊕Z   N   =Y   N =0 N    
     [U F , 0 I ]G N  is added to both sides of the equation, and then [0 F , U I ]G N  ⊕Z N =Y N =[U F , 0 I ]G N , which is equivalent to Û S     c   =Û I =f SC (Y N =[U F , 0 I ]G N , U F =0 F ), is obtained. In this way, the existing polar decoder can be directly used. In addition, in the compression process, bit-by-bit comparison further needs to be performed on Û S     c    and the original U S     c   . If there is a different bit, an error location is recorded, Û i  of the bit is flipped, and bit-by-bit comparison continues to be performed for a next bit. 
     For example,  FIG. 13  is a schematic flowchart of lossless polar compression according to an embodiment of this application.  1301 : Obtain N independent and identically distributed (i.i.d) signals X N  generated by a source.  1302 : Obtain a code sequence [U S , U S     c   ]=U N =X N G N  through polarization processing, where G N  is a polarization matrix.  1303 : Use a set S as a fixed bit set F, use a set S C  as an information bit set I for channel coding, set Y N =[U F , 0 I ]G N , and input Y N  to a polar decoder.  1304 : The polar decoder that sets the fixed bit set to 0 F  performs decoding to obtain an estimated value Û i , where i∈I.  1305 : Determine whether Û i =U i  holds true, and if Û i =U i  does not hold true, perform step  1306 ; or if Û i =U i  holds true, perform step  1307 .  1306 : Flip Û i  and record i in a set T.  1307 : Determine whether i is equal to N, and if i is equal to N, output [U S ,T]; or i is not equal to N, check a next bit. 
     In this embodiment of this application, color transform, grayscale translation, DCT transform, data quantization, zig-zag scanning, and run-length encoding are performed on image data to obtain RLE data, the RLE data is reassembled, reassembled RLE data is converted into a multi-bit binary bit sequence, and finally a polar code is designed to perform parallel compression on a signal of each bit plane. This increases a compression throughput of the polar code and implements fast lossless compression of parallel polar coding. 
       FIG. 14  is a schematic diagram of a coding apparatus according to an embodiment of this application. The apparatus in this embodiment of this application includes at least an obtaining module  1401  and a processing module  1402 . 
     The obtaining module  1401  is configured to obtain a plurality of pieces of run-length encoding (RLE) data and distribution probabilities corresponding to the plurality of pieces of RLE data; 
     the processing module  1402  is configured to: sort the plurality of pieces of RLE data based on the distribution probabilities, and map the plurality of pieces of sorted RLE data onto a plurality of pieces of reassembled data; 
     the processing module  1402  is further configured to: expand the plurality of pieces of reassembled data into a plurality of pieces of binary data, generate a first matrix, and calculate an occurrence probability of a bit 1 in each column in the first matrix based on the distribution probabilities; 
     the processing module  1402  is further configured to determine, based on the occurrence probability, a code sequence obtained by processing a source signal, where the code sequence includes a first set and a second set, the first set is a bit reserved after compression, and the second set is a bit discarded after compression; and 
     the processing module  1402  is further configured to decode a first vector to output a third set, where the first vector is an all-0 sequence, or is a vector obtained by multiplying a vector corresponding to the first set and a polarization matrix, and the third set includes the bit reserved after compression and a location at which a decoding error occurs in the bit discarded after compression. 
     The first set is a bit whose polarized entropy approximates to 1 in the code sequence, and the second set is a bit whose polarized entropy approximates to 0 in the code sequence. 
     The polarized entropy is determined based on the occurrence probability. 
     Optionally, the processing module  1402  is further configured to perform decoding based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =0 N , U F =U S , Y N  is a received signal of the polar decoder, U F  is the fixed bit set, U S  is the first set, and N is an integer greater than or equal to 1. 
     Optionally, the processing module  1402  is further configured to perform decoding based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =[U F , 0 I ,]*G N , U F =0 F , Y N  is a received signal of the polar decoder, U F  is the fixed bit set, G N  is the polarization matrix, and N is an integer greater than or equal to 1. 
     Optionally, the processing module  1402  is further configured to: when the estimated value is different from an original value of the bit discarded after compression, flip the estimated value, and record the location at which a decoding error occurs in the bit discarded after compression. 
     Optionally, the processing module  1402  is further configured to sort the plurality of pieces of RLE data in descending order of the distribution probabilities. 
     Optionally, the processing module  1402  is further configured to: perform layering based on each column of the first matrix to obtain a plurality of bit planes, and calculate the occurrence probability of 1 in each bit plane. 
     It should be noted that for implementation of each module, refer to corresponding description of the method embodiment shown in  FIG. 7 , to perform the method and the function in the foregoing embodiment. 
       FIG. 15  is a schematic diagram of a structure of a network element device according to an embodiment of this application. As shown in  FIG. 15 , the network element device may include at least one processor  1501 , at least one communications interface  1502 , at least one memory  1503 , and at least one communications bus  1504 . 
     The processor  1501  may be a central processing unit, a general purpose processor, a digital signal processor, an application-specific integrated circuit, a field programmable gate array or another programmable logic device, a transistor logic device, a hardware component, or any combination thereof. The processor  1501  may implement or execute various example logical blocks, modules, and circuits described with reference to content disclosed in this application. Alternatively, the processor may be a combination of processors implementing a computing function, for example, a combination including one or more microprocessors, or a combination of a digital signal processor and a microprocessor. The communications bus  1504  may be a peripheral component interconnect (PCI) bus, an extended industry standard architecture (EISA) bus, or the like. The bus may be classified into an address bus, a data bus, a control bus, and the like. For ease of representation, the bus in  FIG. 15  is represented by only one thick line, but this does not mean that there is only one bus or only one type of bus. The communications bus  1504  is configured to implement connection and communication between these components. The communications interface  1502  of the device in this embodiment of this application is configured to perform signaling or data communication with another node device. The memory  1503  may include a volatile memory, for example, a dynamic random access memory (DRAM), a phase-change random access memory (PRAM), or a magnetoresistive random access memory (MRAM). The memory  1503  may further include a nonvolatile memory, for example, at least one magnetic disk storage device, an electrically erasable programmable read-only memory (EEPROM), a flash memory device such as a NOR flash memory or a NAND flash memory, or a semiconductor device such as a solid-state drive (SSD). Optionally, the memory  1503  may be at least one storage apparatus far away from the processor  1501 . Optionally, the memory  1503  may further store a set of program code, and optionally, the processor  1501  may further execute a program stored in the memory  1503 . 
     The communications interface  1502  is configured to obtain a plurality of pieces of run-length encoding (RLE) data and distribution probabilities corresponding to the plurality of pieces of RLE data; 
     the processor  1501  is configured to: sort the plurality of pieces of RLE data based on the distribution probabilities, and map the plurality of pieces of sorted RLE data onto a plurality of pieces of reassembled data; 
     the processor  1501  is further configured to: expand the plurality of pieces of reassembled data into a plurality of pieces of binary data, generate a first matrix, and calculate an occurrence probability of a bit 1 in each column in the first matrix based on the distribution probabilities; 
     the processor  1501  is further configured to determine, based on the occurrence probability, a code sequence obtained by processing a source signal, where the code sequence includes a first set and a second set, the first set is a bit reserved after compression, and the second set is a bit discarded after compression; and 
     the processor  1501  is further configured to decode a first vector to output a third set, where the first vector is an all-0 sequence, or is a vector obtained by multiplying a vector corresponding to the first set and a polarization matrix, and the third set includes the bit reserved after compression and a location at which a decoding error occurs in the bit discarded after compression. 
     The first set is a bit whose polarized entropy approximates to 1 in the code sequence, and the second set is a bit whose polarized entropy approximates to 0 in the code sequence. 
     The polarized entropy is determined based on the occurrence probability. 
     Optionally, the processor  1501  is further configured to perform the following operation: 
     performing decoding based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N =0 N , U F =U S , Y N  is a received signal of the polar decoder, U F  is the fixed bit set, U S  is the first set, and N is an integer greater than or equal to 1. 
     Optionally, the processor  1501  is further configured to perform the following operation: 
     performing decoding based on a fixed bit set by using a polar decoder, to obtain an estimated value of the bit discarded after compression, where Y N  [U F , 0 I ]*G N , U F =0 F , Y N  is a received signal of the polar decoder, U F  is the fixed bit set, G N  is the polarization matrix, and N is an integer greater than or equal to 1. 
     Optionally, the processor  1501  is further configured to perform the following operations: 
     when the estimated value is different from an original value of the bit discarded after compression, flipping the estimated value, and recording the location at which a decoding error occurs in the bit discarded after compression. 
     Optionally, the processor  1501  is further configured to perform the following operation: 
     sorting the plurality of pieces of RLE data in descending order of the distribution probabilities. 
     Optionally, the processor  1501  is further configured to perform the following operations: 
     performing layering based on each column of the first matrix to obtain a plurality of bit planes, and calculating the occurrence probability of 1 in each bit plane. 
     Further, the processor may further cooperate with the memory and the communications interface to perform operations of the network element device in the foregoing embodiments of this application. 
     An embodiment of this application further provides a processor. The processor is coupled to a memory, and is configured to perform any method and function that are related to the network element device in the foregoing embodiment. 
     An embodiment of this application further provides a computer program product including instructions. When the computer program product runs on a computer, the computer is enabled to perform any method and function that are related to the network element device in the foregoing embodiment. 
     An embodiment of this application further provides an apparatus, configured to perform any method and function that are related to the network element device in the foregoing embodiment. 
     All or some of the foregoing embodiments may be implemented by software, hardware, firmware, or any combination thereof. When software is used to implement the embodiments, all or some of the foregoing embodiments may be implemented in a form of a computer program product. The computer program product includes one or more computer instructions. When the computer instructions are loaded and executed on a computer, the procedure or functions according to the embodiments of this application are completely or partially generated. The computer may be a general-purpose computer, a special-purpose computer, a computer network, or another programmable apparatus. The computer instructions may be stored in a computer-readable storage medium or may be transmitted from a computer-readable storage medium to another computer-readable storage medium. For example, the computer instructions may be transmitted from a website, computer, server, or data center to another website, computer, server, or data center in a wired (for example, a coaxial cable, an optical fiber, or a digital subscriber line (DSL)) or wireless (for example, infrared, radio, or microwave) manner. The computer-readable storage medium may be any usable medium accessible by a computer, or a data storage device, such as a server or a data center, integrating one or more usable media. The usable medium may be a magnetic medium (for example, a floppy disk, a hard disk, or a magnetic tape), an optical medium (for example, a DVD), a semiconductor medium (for example, a solid-state drive (SSD)), or the like. 
     The objectives, technical solutions, and beneficial effects of this application are further described in detail in the foregoing specific implementations. Any modification, equivalent replacement, improvement, or the like made without departing from the spirit and principle of this application shall fall within the protection scope of this application.