TWI491178B - Tail-biting convolutional decoder and decoding method - Google Patents

Description

Decoded decoder and decoding method

The present invention relates to wireless communication devices and, more particularly, to techniques for reducing decoding errors in wireless communication devices.

In a receiving device, a Viterbi decoder is often used to decode a convolutional code encoded with forward error correction (FEC). Since the receiver does not know the signal sent by the original transmitting end, and the original signal has been changed by the nature of the wireless channel (such as noise, attenuation, rain, etc.), the bit in the original signal is said to be hidden.

The concept of the Viterbi algorithm is to find the most likely sequence of hidden states, such as finding the most likely sequence of the state of the hidden Markov model (for the Markov model, see Forney et al. in Proceedings of the IEEE publication). "The Viterbi algorithm", Vol. 61, No. 3, pp. 268-278, March 1973).

Forward error correction and Viterbi decoders are particularly useful when the receiver is performing error correction procedures, or when feedback from the receiver to the transmitter is not feasible. Viterbi decoders are widely used in wireless communications, such as cellular and satellite communications, voice recognition, storage confirmation, and more. The long term evolution (LTE) mobile communication system proposed by the 3rd generation partnership project (3GPP) uses the whirling code to improve the decoding reliability of the control channel (refer to the third generation partner). Plan technical document No. 36.212).

In a wireless communication receiver, a detector is used to generate a signal that is provided to the Viterbi decoder. The Viterbi decoder must determine whether the bit in the signal is zero or one. The signal may be a binary signal or a probability value, the former being applied to a hard decision and the latter being applied to a soft decision. The hard decision is made by comparing the signal strength, and the soft decision is based on the likelihood model.

For each possible state, the Viterbi decoder records the most probable path in the trellis associated with the convolutional code, thereby generating a maximum likelihood sequence estimate for the signal sent by the transmitting end. , referred to as MLSE). These most probable paths are also referred to as surviving sequences and are used to generate decoded bit sequences. There are two ways to generate these sequences: the scratchpad exchange method and the traceback method (refer to Feygin, G. et al., IEEE Transactions on Communications, Vol. 41, No. 3, pp. 425-429, "Architectural tradeoffs for survivor". Sequence memory management in Viterbi decoders"). The concept of the scratchpad exchange method is simpler, but requires a larger memory access; the traceback method is therefore more commonly used.

To assist the Viterbi decoding process, the state of the whirling code encoder is often stored in the value 0 to force the start state of the Viterbi trellis handler to equal 0 and initialize the paths associated with the different states. index. Similarly, by adding a plurality of bits 0 to the end of the message, the final state of the encoder is also often forced to zero.

Since the decoder can use this information to determine which survival sequence to select to generate the decoded bit, forcing the final state of the encoder to zero improves performance. The number of extra bits required to force the final state of the encoder to zero is equal to the memory length of the encoder or the length limit of the encoder itself. In other words, the encoder is "filled" with bit 0. A convolutional code that fills the encoder with a known value is called a "tailed" convolutional code.

Since extra bits are added to the message, the cost of using tailed convolution to improve performance is that spectral efficiency is reduced. If the message length is long, the spectral efficiency degradation is small and negligible; but when the message length is short, the effect of the spectral efficiency reduction becomes obvious.

Therefore, when the message length is short, it is necessary to avoid forcing the final state of the encoder to be 0 or other fixed value. If you want to avoid the degradation of the spectrum efficiency, you can use the tail-biting convolutional code (refer to Ma et al., IEEE Transactions on Communications, Vol. 34, No. 2, pp. 104-111, "On Tail Biting Convolutional Codes". "). The tail-to-tail revolving code does not force the initial and final states of the encoder to be set to a preset value, but ensures that the two states are identical. More specifically, the truncated convolutional code initializes the state of the encoder with the last few bits of the message itself.

The tail-to-tail spin code provides similar performance to the tailed spin code without causing spectral efficiency degradation. Therefore, the deciphering convolutional code is often used for the encoding of shorter messages, and is also used to protect certain control channels, such as the physical broadcast channel (PBCH) or physical downlink control defined in the 3GPP LTE standard. The physical downlink control channel (referred to as PDCCH).

However, the coding complexity of the de-spinning code is higher. For example, the maximum likelihood detector (MLD) of the tail-reversal code needs to perform S-dimensional Viterbi decoding operations, and each time the initial and final states of the encoder must be assumed, where S represents and maneuvers. The total number of states in the code-dependent format structure. The best of the S different possibilities will be used to generate the decoding bit (for details, see "Two Decoding Algorithms for Tailbiting" by Shao et al., IEEE Transactions on Communications, Vol. 51, No. 10, No. 1658-1665. Codes)). At present, there are some decoding algorithms with less effect but lower complexity. For details, please refer to "An Efficient Adaptive Circular Viterbi Algorithm for Decoding" published by Cox et al., IEEE Transactions on Vehicular Technology, Vol. 3, No. 1, pp. 57-68. "Generalized Tailbiting Convolutional Codes", and "Research on An-Based Decode of tail-biting convolutional codes and Their Performance Analyses Used in 1999, by Zhang et al., International Forum on Information Technology and Applications, Vol. 2, pp. 303-306. LTE System".

The technical solution proposed by the present invention uses the information in the data stream received by the receiver that has not been used or obtained by the gyro decoder to decode the tail-back gyro code, such as cyclic redundancy check (CRC) information or other transmission. Information that both the terminal and the receiver know. In addition, a single parallel trace is used to reduce the complexity of implementing this solution. Again, the least reliable decision made in the forward processing procedure can be preserved to generate additional candidate coded characters. The technical solution proposed by the invention can reduce the false detection rate (FDR) and/or the detection error rate (DER).

In an embodiment in accordance with the invention, the data received by the communication device includes a message encoded with a tail-back convolutional code. First, the data is detected to find a block of code having a specific data length. Subsequently, the code block is subjected to one or more forward processing iterations to generate information representative of a state diagram and to identify a plurality of paths from the plurality of end states to the plurality of start states in the state diagram. The information representing the state map corresponds to a plurality of state transitions that may be generated by an encoder when encoding the message.

Then, for the state diagram, a single parallel traceback operation is performed from the plurality of end states along the identified plurality of paths to determine when at least one end state and a start state are in a particular path of the state diagram. Match. Subsequently, when the single parallel traceback operation finds that an initial state coincides with a corresponding one of the end states, one or more first candidate coded characters are generated. Next, one or more correctly encoded characters are identified from the one or more first candidate coded characters. The message is then generated based on one or more correctly encoded characters.

This message can also be applied with a cyclic redundancy check code. When a first candidate coded character passes a cyclic redundancy check condition, one or more correctly coded characters are recognized. The cyclic redundancy check condition can be a cyclic redundancy check mask used by known encoders.

In another example, the method further calculates a quality metrics (QM) for each of the first candidate coded characters, and the one or more correctly encoded characters are based on the one or more qualities. The metric is selected.

When performing one or more forward processing iterations, it may include tracking one or more locations in the state map that correspond to one or more of the least reliable state transition decisions. Correspondingly, during the single parallel traceback operation, one or more of the least reliable state transition decisions may be reversed by inverting one or more of the state diagrams to generate one or more second candidate coded characters. . Moreover, the method can further calculate a quality metric for each of the second candidate coded characters and select the one or more correctly encoded characters based on the one or more quality metrics.

The information can include a known bit information. During the iterative processing of iterations, the state transitions in the state table can be forced to conform to the known bit information. Alternatively, the known bit information can be used to exclude one or more candidate coded characters that do not conform to one or more states corresponding to the known bit information.

The advantages and spirit of the present invention will be further understood from the following detailed description of the invention.

Referring to FIG. 1, the wireless communication system 100 illustrated in FIG. 1 includes a base station 110 and a plurality of mobile devices 120(1)-120(Z). The base station 110 can be connected to other wired data network facilities (not shown) and used as a gateway or access point to enable the mobile devices 120(1)-120(Z) to connect to the wired data. Internet facilities.

The base station 110 includes a plurality of antennas 140(1)-140(M), and the mobile devices 120(1)-120(Z) include a plurality of antennas 130(1)-130(N). The base station 110 can wirelessly communicate with the mobile devices 120(1)-120(Z) individually using a broadband wireless communication protocol having a bandwidth much greater than the coherence bandwidth.

For example, the broadband wireless communication protocol may be a time division-synchronous code division multiple access (TD-SCDMA) communication protocol, or a time division long term evolution (referred to as time division long term evolution, referred to as TD-LTE) communication protocol.

The techniques provided by the present invention can assist a wireless communication device (e.g., a base station or mobile device) to decode messages received from other wireless communication devices using Viterbi and a cyclic redundancy check (CRC) decoder. For example, if base station 110 in FIG. 1 transmits a message to mobile device 120(1), mobile device 120(1) can decode the received message using the techniques described below, and can then transmit a response to the base. Taiwan 110.

Please refer to the Viterbi and Cyclic Redundancy Check Encoder shown in Figure 2. The message 210 is sent to the message generator 220. The output of the message generator 220 is then provided to a cyclic redundancy check encoder 230; the cyclic redundancy check encoder 230 can employ a cyclic redundancy check mask 235. After the cyclic redundancy check is completed, the output of the cyclic redundancy check encoder 230 is supplied to the cyclotron encoder 240 and then to the transmitter 250. It will be appreciated by those of ordinary skill in the art that it is possible to insert other intermediate programs that do not affect the following procedures, such as adding a rate matching program between the cyclotron encoder 240 and the transmitter 250. In order to reduce the false detection rate (FDR) and/or the detection error rate (DER), the message 210 may have a data field known to both the transmitting end and the receiving end.

The forward error correction (FEC) encoder uses a convolutional code system defined by two parameters: code rate and limit length.

The code rate refers to the ratio of the number of input bits of the whirling encoder 240 divided by the number of output channel symbols in one coding cycle. A small code rate indicates a high degree of redundancy, which provides better error control at the expense of a larger encoded data bandwidth. For example, if the input bit sequence Ck passes through three encoding paths, and each encoding path produces one output bit, the encoder has a code rate of 1/3.

In this example, the bit sequence _Ck is sequentially passed through the six bit delays 260(1)-260(6) in the whirling encoder 240 under the control of the clock signal. In addition, the bit sequence C _k is also input to a series of exclusive-OR (XOR) gates (represented by the symbol ⊕). In the encoding path 280(1), the input bit sequentially and the output signals of the bit delays 260(2), 260(3), 260(5), 260(6) are subjected to a mutually exclusive OR operation. The encoding process is defined as the function G ₀ . The coding function G ₀ can also be expressed as a polynomial G ₀₌ 1+x ² +x ³ +x ⁵ +x ⁶ , wherein the last four terms correspond to the bit delays 260(2), 260(3, respectively. ), 260(5), 260(6), making the first item 1 is a general rule.

For ease of explanation, this convolutional code is broken down into three phases. Between time points 270(1) and 270(2), there is no exclusive or gate corresponding to bit delay 260(1) in encoding path 280(1), only corresponding to bit delay 260(2), 260 (3) mutual exclusion or gate. If 0 is used to indicate a bit delay without a corresponding mutex or gate, and 1 is a bit delay with a corresponding mutex or gate, the delay at this stage can be represented as 011b or octal. Expressed as 3 ₈ .

Between time points 270(1) and 270(2), three mutually exclusive transitions corresponding to bit delays 260(1), 260(2), 260(3), respectively, in encoding path 280(2) Or gate, so it is represented as 111b or 7 ₈ . There is no mutual exclusion or gate corresponding to the bit delay 260(3) in the encoding path 280(3), and only the pair passes through the mutual exclusion or gate corresponding to the bit delays 260(1), 260(2), It is expressed as 110b or 6 ₈ . Similarly, between time points 270(2) and 270(3), the bit delays of the above three encoding paths can be represented as 011b or 3 ₈ , 001b or 1 ₈ , and 101b or 5 _{8 , respectively} .

Therefore, the function G ₀ can also be reduced to 133 ₈ , where 1 represents the first term in the equation. Similarly, the function G ₁ =1+x ¹ +x ² +x ³ +x ⁶ can be reduced to 171 ₈ , and the function G ₂ =1+x ¹ +x ² +x ⁴ +x ⁶ can be simplified to 165 ₈ . This type of cyclotron encoder can be found in section 5.1.3.1 of the third generation partner project technical document No. 36.212.

Bit delays 260(1)-260(6) may actually be complementary flip-flops. The next input bit _Ck is supplied to the bit delay 260(1) every time a clock cycle elapses. At the same time, the original input bit of bit delay 260(1) will be sent to bit delay 260(2), and so on. The bit values in the bit delays 260(1)-260(6) represent the state of the encoder during each clock cycle. Since there are six bit delays, the cyclotron encoder 240 has 26 (i.e., 64) possible states, equivalent to a finite state machine. According to the polynomial functions G ₀ , G ₁ , G ₂ , in each clock cycle, the state of the encoder and the current input bits are used to generate output bits d _k ⁽⁰⁾ , d _k ⁽¹⁾ and d _k ⁽²⁾ . The decoder at the receiving end shall regenerate the state of the encoder at the time of encoding based on the received bit. From the perspective of the decoder, the possible states of the encoder can be represented as a trellis diagram. Since the decoder does not know the state of the encoder, the decoder must assume a state transition that may occur in the encoder when the sequence is generated, based on the received sequence of bits.

Referring to Figure 3(A), the format structure of a long-term evolutionary convolutional code is represented as a binary butterfly diagram 310(1)-310(32). These thirty-two butterfly diagrams contain multiple pairs of states that, when combined, become the sixty-four states of the decoder. This format structure is a schematic diagram of the information stored in the decoder memory. It should be noted that the format structure in FIG. 3(A) has been simplified for the convenience of the reader, and it is not intended to accurately describe the state connection between the butterfly patterns or the number of states when actually decoding.

As can be seen from Figure 2, one advantage of the whirling code is that its structure is highly repetitive, thus providing a symmetrical code tree. This symmetry feature reduces the number of states that need to be evaluated when looking for a possible path corresponding to a sequence of data (eg, _Ck ). In addition, when decoding a symmetric code, for each of the sixty-four possible encoder states, only the most probable path (ie, the surviving path) will be considered, and the other paths will be ignored.

Viterbi decoders operating in accordance with these coding characteristics are like finite state machines with finite set state transitions. The decoder can assume each possible encoder state and determine the probability of the encoder transitioning from one state to another based on the received encoded data string with noise.

The format structure of Figure 3(A) presents an example of a coded block that handles a certain number of states. In step 330, the Viterbi decoding process begins with one or more forward processing steps. The forward processing is illustrated as being performed from left to right in the figure and may begin when a set of symbol data containing a particular number of symbols is received.

Therefore, the leftmost state is the start state and the rightmost state is the end state. In the process of forward processing, multiple paths to the format structure are found, and metrics corresponding to these paths are stored. The metric can include path metrics (PM), path history, branch metrics (BM) metrics, quality metrics (QM), and the least reliable. The location of the branch decision (decision method is detailed later).

In step 340, the trace-back process begins with a single parallel trace-back. Parallel traceability is traced back to right from left to left, depending on the stored metrics, along the format structure, from multiple end states.

For a whirling code, parallel tracing will find multiple starting states. For the tail-to-tail spin code, since the encoder uses the trailing bit of the message as the start, the start state must be the same as the end state. A traceback path with a different starting state than the ending state will be ignored. The output of the traceback process contains one or more candidate coded characters, as well as updated quality metrics.

In this example, the traceback process finds a possible path 320 that is the same as the start state and the end state. As indicated below in Figure 3(A), the forward processing and the traceback processing are collectively referred to herein as Viterbi forward processing and parallel traceability procedure 900a. The introduction of Viterbi's forward processing and parallel tracing program 900a will be related to Figure 3 (B), Figure 4, Figure 5, Figure 6, Figure 7 (A), Figure 7 (B), Figure 8, and Figure 9 (A) is described in detail.

In step 350, the selection of the code character program begins and is indicated by the dashed box as the code character selection program 900b. By performing a parallel traceback operation, the available candidate codewords will be more than the candidate codewords produced by the general cyclotron code. The increase in the number of candidate code characters will improve the missed detection rate (MDR), but it will also increase the false detection rate (FDR), resulting in erroneous decoding results.

To mitigate the increase in false positive rate, the code character selection procedure 900b employs a variety of techniques to reduce the number of candidate coded characters. The introduction of the code character selection program 900b will be related to FIG. 3(B) and FIG. 8, and will be described in detail in FIG. 9(B).

Figure 3 (B) is used to present the details of the butterfly chart 360 in Figure 3 (A). Butterfly Map 360 presents a selection of branch metrics and path metrics in a standard butterfly icon. The probability of transitioning from one state to another is quantized and referred to as a metric. Metrics and similarity logarithms (log-likehood ratios, referred to as LLRs, used in soft decisions) may be proportional. The higher the metric, the greater the chance of occurrence. The path metric (PM) represents the relative probability that a symbol is transmitted through a particular state. The branch metric (BM) represents the conditional probability of transitioning from a particular original state to a particular target state (assuming the original state is correct).

At any time k for any state S, the Viterbi algorithm calculates two path metrics PM of the same steering state S, thereby determining which is the survival path; in the Viterbi forward processing and parallel tracing procedure 900a, The survival path and its metrics are stored. This is equivalent to storing the corresponding original state for each target state.

During the traceback process, the information needed to generate the survival path is usually stored in the path history (PH) memory, where a bit represents a state to indicate which of the two possible states. One was chosen. The Viterbi forward processing and parallel trace program 900a can perform these operations using an add-compare-select (ACS) unit. The add-compare-select unit is responsible for calculating the values of the state metrics, and finding the relationship between the target state and the original state by using the branch metric.

In addition to the branch metric BM and the path metric PM, the butterfly diagram also references two new parameters: the least reliable metrics (LRM) and the least reliable position (LRP). ). Similar to the path metric, both parameters are updated at each time k at which the state transition occurs.

During forward processing, the least reliable location of each path is updated as the "most unreliable decision" position for each conversion. The least reliable metric is considered to be the credibility associated with the least reliable decision and will be updated during forward processing. The set of credibility associated with each state is first initialized to a large value that is set to be greater than the absolute value of the maximum difference D of the path metric corresponding to a single merge state (using known, Regarding the format structure of the convolutional code and the similarity of the input, the maximum amplitude of the logarithmic LLR value, which can be derived in advance). The least reliable decision position value is set equal to an initial value corresponding to the start of the Viterbi forward processing.

After the first Viterbi forward processing conversion, this set of least reliable decisions on location and confidence was updated in the following manner. As shown in Figure 3 (B), for each state, the absolute value of the difference between the candidate path metrics corresponding to the two leading states can be calculated as follows:

D=|(BM0-BM1)+(PM(2s,k)-PM(2s+1,k))|.

If the absolute value D of this difference is greater than the credibility of the least reliable decision of the winning lead state, the new least reliable decision information for this state will be set to the least reliable decision information equal to the winning lead state.

In contrast, if the absolute value D of the path metric difference is less than the credibility of the winning lead state, the new least reliable decision credibility will be set equal to the path metric difference absolute value D, and the new most unreliable The decision position is set to be equal to one of the indicators corresponding to the position of the transition being processed, as shown by the virtual code in the upper right corner of Figure 3 (B). These processing stages are repeated until the Viterbi forward processing program ends.

Referring to FIG. 4, FIG. 4 is a block diagram showing a format of a forward and reverse (trace) procedure according to the present invention. In this embodiment, the same code block is repeatedly decoded in the forward direction three times. Each iteration represents a generation, and after each forward processing iteration, the metrics corresponding to the different states in the symbol and format structure received by the decoder are updated. A single parallel traceback will be performed after all forward processing iterations are completed. Single parallel tracing reduces the complexity of implementation and can also generate more candidate coded characters to improve the performance of missed detection rates. Parallel traceability is shown in Figure 5.

Referring to Figure 5, the entire coding block is subjected to a single parallel trace from right to left. At stage 500, the traceback begins with multiple end states. This traceback continues until one or more initial states are reached. End states 510-540 correspond to different candidate paths to find possible coded characters. However, only the end state 510 and the end state 530 have matching start states 550, 560 (located at the beginning of the coded block). At this time, the code character selection program 900b must select the more correct one of the two candidate code characters. To achieve this goal, the code character selection program 900b may include one or more cyclic redundancy checks. Execution of the cyclic redundancy check may employ one or more cyclic redundancy check masks 235.

Different cyclic redundancy check masks can be used for different mobile devices, different mobile device groups, or specific message types. The decoder may perform a cyclic redundancy check on the received information bits, and then perform a mutual exclusion or (XOR) procedure on the generated cyclic redundancy check and the received cyclic redundancy check, thereby obtaining a candidate mask. Based on the comparison of the candidate mask with the known mask, it can be further determined whether the currently tested code character is correct. In another example, the decoder knows the type of the message based on the transmitted information, and then determines why the cyclic redundancy check mask.

The number of cyclic redundancy checks is limited to less than the maximum number of possible tail-out coded characters. The N de-tailed coded characters that accept the cyclic redundancy check are sequentially selected, and the order is only related to the position of the state corresponding to each of the coded characters. This approach reduces implementation complexity by avoiding complex sorting operations. To randomize the state of the selected truncated coded character, a set of patterns that vary with the decoding pattern can be used. The maximum number of truncated coded characters that accept cyclic redundancy checks can be designed to be associated with the decoded type, while balancing the false positive rate with the missed detection rate.

In another example, for each candidate coded character, a quality metric QM will be calculated and the quality metric QM will be used to select the output coded character. The quality metric QM can be calculated based on the final path metrics for different states. For example, quality metrics can be calculated using the following equation:

QM=(PM _STATE -PM _MIN )/(PM _MAX -PM _MIN ).

Among them, PM _STATE , PM _MIN , and PM _MAX represent path metrics in different states. Candidate coded characters may be required to have quality metrics that meet or exceed a predetermined threshold. Alternatively, quality metrics may be used to evaluate candidate coded characters and select one or more output coded characters based on the ratings.

Figure 6 is an illustration of an example of performing "bit forcing" during forward processing. At stage 600, the bit information in the encoded character is known. For example, the physical broadcast channel PBCH or the physical downlink control channel PDCCH channel defined in the 3GPP LTE specification may use a data field known by the decoder. During forward processing, the decoder can force a format structure conversion that conforms to a known bit field. Alternatively, based on the status of the known bit field information, the program 900 may filter out candidate coded characters that do not match the status during the traceback period.

It should be noted that the known information related to the transmission of information may also be knowledge related to the incorrect sequence, and it is not necessarily the knowledge that certain bits in the transmitted message must be specific values. For example, if a message contains multiple fields in series, the correct number of fields may be lower than the number of sequences that can be represented by the bit field (for example, the number of correct items is less than 2) Square, the number of powers is the number of bits in the field). In this case, incorrect candidate codewords can be filtered out by excluding sequences that do not correspond to any of the possible transmission sequences.

In yet another embodiment, the known bit field information can be used to limit the possible starting state. For example, if the number of known bits is greater than or equal to the memory length of the encoder, the format structure state of the location corresponding to the known bit field information will be known to the receiver. Therefore, by performing format structure processing from the position of the known bit field, the initial state can be forced to be equal to the state corresponding to the bit field or a part of the bit field (if the number of known bits is greater than Encoder memory), and the trace program only needs to be done for the end state corresponding to this bit field.

It is worth noting that since the format structure of the deciphering code is cyclic, the format structure processing can start from any position of the bit sequence. If the number of known bits is absolutely smaller than the encoder memory, the start/end state is not completely known, however, it is still possible to exclude the state of the information that does not conform to the known bit field.

Please refer to another embodiment of the Viterbi forward processing and parallel traceability procedure 900a illustrated in Figures 7(A) and 7(B) to illustrate how to trace the least reliable decision. The least reliable decision is the decision when the two path metrics are fairly close (ie, the path metrics are very small); therefore, the chances of the two states being selected are comparable, similar to the chances of a positive and negative face loss. When the probability of the two is similar, a state decision is likely to be incorrect, that is, less reliable.

At stage 700, the forward processing begins. At stage 710, a least reliable decision is identified and its location is stored (as described above). In the case of performing multiple Viterbi forward processing iterations, the generation of the least reliable decision information can be limited to the last iteration.

Through tracing, the least reliable location corresponding to each state is used to generate an alternate path. Referring to Figure 7(B), in stage 720, a trace program is used to find an incorrect path that does not match the start and end states. The least reliable decision information is stored in stage 710, so the code character selection program 900b can override and reverse the decision made during the forward processing. At stage 730, the state branch decision is reversed based on the path of the decision bit stored in the path history that coincides with the established start and end states, thereby increasing the chances of finding the correct coded character.

In order to simplify the drawing, Figure 7(B) only presents a decision inversion; it should be understood that the inversion of the least reliable decision can be performed in each of the multiple parallel traceback operations, so the number of parallel traces Up to twice the number of states.

In order to reduce the complexity and/or false positive rate, the most unreliable decision to perform the inversion may be for only a few of the S states. For example, the execution of the inversion is only for the state that the least reliable decision metric is below a certain threshold. Alternatively, the least reliable decision to reverse can also be performed only for the L states with the lowest metric (L is less than S).

When the quality metric is used to select the output coded character, a quality metric can be generated for the candidate output coded character that is generated using the least reliable decision inversion. If QM=(PM _STATE -PM _MIN )/(PM _MAX -PM _MIN ) represents a quality metric corresponding to a particular state, the candidate output coded characters generated by the least reliable decision inversion may be calculated according to the following equation: Quality metric value:

QM = (PM _STATE - PM _{MIN -} LRM _STATE ) / (PM _MAX - PM _MIN ).

Alternatively, this metric can be determined according to the following equation:

Max{(PM _STATE -PM _MIN -LRM _STATE )/(PM _MAX -PM _MIN ), 0}.

As mentioned above, these metrics can be used to select output coded characters. Alternatively, the same quality metric may be used for two candidate codewords generated according to the same state, and the least reliable decision inversion is not used when selecting the coded character.

It should be noted that the least reliable decision to reverse can be further extended to: the generation of candidate codewords, not only based on the least reliable decision corresponding to a particular end state, but according to the corresponding state The M most unreliable decisions.

During the traceback period, the increase in the number of candidate coded characters by inverting multiple unreliable decisions for each end state increases the miss detection rate performance. This approach increases the false positive rate, but this disadvantage can be eliminated by several solutions proposed by the present invention, that is, performing further checks on candidate coded characters.

The following is an extension of the "most unreliable decision reversal" with the case of M=2. According to this example, those of ordinary skill in the art to which the present invention pertains can understand other cases of M>2.

It is assumed that three candidate coded characters are generated for each state: one of the most likely paths to the coded character, and two of the coded characters that correspond to the most unreliable decision. For each state S _s , each conversion k, the following four metrics are calculated:

● LRM0 (S _s , k): metrics related to the least reliable decision

● LRM1 (S _s , k): metrics related to the second least reliable decision

• LRP0(S _s , k): the most unreliable decision position, corresponding to a value indicating the most unreliable conversion indicator in the format structure

● LRP1 (S _s , k): The second most unreliable location. In some cases, the second least reliable decision may be a divergence corresponding to the most probable path; the metric LRP1(S _s , k) may be generated from a single conversion indicator. Alternatively, the second least reliable decision may result from the inversion of two decisions corresponding to the most probable path. In these cases, the metric LRP1(S _s , k) is generated based on the two conversion inversions generated by the third most probable path.

How to generate metrics LRM0(S _s ,k+1), LRM1(S _s ,k+1), LRP0(S _s ,k+1) and LRP1(S _s ,k+1) for state S _s will be described later. . The two states that are merged into state S _s are labeled as S _l0 and S _l1 . General without loss of condition, the path is assumed to calculate _{PM (S s, n + 1} ) metrics of the comparison process, is selected as the state with the state of S _l0. In the single inversion case, as shown in FIG. 3(B), the least reliable determination metric LRM0(S _s , k+1) and the corresponding position LRP0(S _s , k+1) are calculated. First, a metric D is calculated to quantify the reliability of the decisions made in the selection of the latest path metrics:

D=|(BM0-BM1)+(PM(S _l0 ,k)-PM(S _l1 ,k))|.

This metric D is compared to LRM0 (S _l0 , k). LRM0(S _s ,k+1) and LRP0(S _s ,k+1) can be calculated according to the following equation:

_{If (D <LRM0 (S l0} , k)) {

LRM0(S _s ,k+1)=D

LRP0(S _s ,k+1)=k+1}

Else{

LRM0(S _s ,k+1)=LRM0(S _l0 ,k)

LRP0(S _s ,k+1)=LRP0(S _s ,k)}

The calculation of LRM1(S _s , k+1) and LRP1(S _s , k+1) is then related to which of the above two tests wins.

First, the calculation in the first condition D < LRM0 (S _l0 , k+1) will be described. The second most unreliable metric can be calculated as follows:

If(LRM0(S _l0 ,k)<f(D,LRM0(S _l1 ,k))){

LRM1(S _s ,k+1)=LRM0(S _l0 ,k)

LRP1(S _s ,k+1)=LRP0(S _l1 ,k)}

Else{

LRM1(S _s ,k+1)=f(D,LRM0(S _l1 ,k))

LRP1(S _s ,k+1)={k+1, LRP0(S _l1 ,k)}

The function f(x, y) is a combination of two reliability metrics x, y to produce a reliability metric. Those of ordinary skill in the art to which the present invention pertains will appreciate that there are many possibilities for the function f(x, y). For example, the function f(x, y) can be f(x, y) = x + y or f(x, y) = log(exp(x) + exp(y)).

The calculation of the metrics LRM1(S _s , k+1) and LRP1(S _s , k+1) for the second case (generating the least reliable decision metric) will be explained below. The metrics LRM1(S _s ,k+1) and LRP1(S _s ,k+1) are calculated as follows:

If(D<LRM1(S _l0 ,k)){

LRM1(S _s ,k+1)=D

LRP1(S _s ,k+1)=k+1}

Else{

LRM1(S _s ,k+1)=LRM1(S _l0 ,k)

LRP1(S _s ,k+1)=LRP1(S _l0 ,k)}

Please refer to FIG. 8, which is a block diagram illustrating a wireless communication device (eg, base station 110 or mobile device 120) for Viterbi and code character selection methods. FIG. 8 illustrates the Viterbi and cyclic redundancy check decoding scheme by taking the mobile device 120(1) as an example; it should be noted that the base station 110 can also implement this scheme.

Mobile device 120(1) includes a transmitter 820, a receiver 830, and a controller 840. Controller 840 is operative to provide the data to be transmitted to transmitter 820 and to process the signals received by receiver 830.

In addition, controller 840 is also responsible for other control functions for transmission and reception. Some of the functions of transmitter 820 and receiver 830 can be implemented using a data machine; other functions of transmitter 820 and receiver 830 can be implemented with radio frequency transmitters and radio frequency transceiver circuits. It should be noted that in each signal path, an analog to digital converter for converting an analog signal and a digital signal, and a digital to analog converter are provided.

Transmitter 820 can include a plurality of transmit circuits, each providing an up-converted signal to one of a plurality of antennas 130(1)-130(N) for transmission. The receiver 830 includes a detector 860 for detecting signals received by the antennas 130(1)-130(N) and providing detection results (such as similarity proportional logarithmic data) to the controller 840.

It should be noted that the receiver 830 may include a plurality of receiving circuits, each corresponding to one of the plurality of antennas 130(1)-130(N). These individual receiving circuits are not shown. The controller 840 includes a memory 850 or other data storage block for storing the data required by the technical solution. The memory 850 can be external to the controller 840 or can be included in the controller 840. The instructions for executing the Viterbi forward processing and parallel trace program 900a and the encoded character selection program 900b may be stored in the memory 850 for execution by the controller 840.

The functionality of controller 840 can be implemented using one or more tangible, rather than transient, media (eg, embedded logic for a particular application integrated circuit, digital signal processor instructions, software that can be executed by the processor). . The memory 850 stores data required for the various operations described above (and/or stores software or processor instructions that implement the above operations). The Viterbi forward processing and parallel trace program 900a and the code character selection program 900b can be implemented using fixed logic or programmable logic circuitry (eg, software/computer instructions executed by the processor).

Referring to Figure 9(A), the Viterbi forward processing and parallel traceability procedure 900a will be described below. Step 910 is to receive data containing a message encoded with a deciphering convolutional code. This message can be encoded by a cyclic redundancy check; this cyclic redundancy check code can use one of a plurality of known cyclic redundancy check masks. Step 920 is to detect the data to find a coded block having a specific data length. In step 930, the coded block is subjected to one or more forward processing iterations to generate information representative of a state diagram and to identify paths from the plurality of end states to the plurality of start states in the state diagram. The state diagram corresponds to a plurality of state transitions that may be generated when an encoder generates the message.

Step 940 is to perform a single parallel traceback operation on the state diagram from the plurality of end states along the corresponding path to determine when at least one of the end states in the particular path of the state diagram matches an initial state. Step 950 is to generate one or more first candidate coded characters when the single parallel traceback operation finds that an initial state matches a corresponding one of the end states.

Referring to FIG. 9(B), the code character selection program 900b will be described below. Step 960 is to identify one or more correctly encoded characters from the one or more first candidate coded characters. In step 970, when a first candidate coded character passes a cyclic redundancy check condition or conforms to a quality metric criterion, one or more correct coded characters may be further derived from the one or more first candidate coded characters. Was selected.

As described above, the cyclic redundancy check condition can utilize one of a plurality of known cyclic redundancy check masks. The coded character selection program 900b may also utilize quality metrics and bit force techniques to reduce candidate coded characters. Step 980 is to generate the message based on one or more correctly encoded characters.

In order to balance the miss detection rate/false positive rate performance, various technical solutions disclosed by the present invention can be combined. Some of the foregoing schemes, such as parallel traceability from multiple end states, forcing a bit to conform to a known bit to conform to a forward processing decision, and generating a candidate coded character based on the least reliable decision, at the expense of a false positive rate To improve the performance of missed detection rates.

In addition, the use of quality metrics or incorrect field values to exclude candidate coded characters reduces the false positive rate at the expense of poor miss detection rate performance. Therefore, the receiver can decide which programs to adopt based on the expected false positive rate/missing detection rate and transmission status. For example, when the receiver uses multiple cyclic redundancy check masks to perform cyclic redundancy checks, the false positive rate increases as the number of masks in the measured data increases.

Therefore, when the number of cyclic redundancy check masks is large, the receiving program can be designed to adopt a program that reduces the false positive rate. Or, for some channels, the cost of missing a correct reception may be higher than the cost of decoding to produce a correct message. In such a case, a program that can reduce the miss detection rate can be selected, even if the false positive rate is increased.

The above description of the preferred embodiments is intended to be illustrative of the nature and spirit of the invention and is not intended to limit the scope of the invention. On the contrary, the intention is to cover various modifications and equivalents within the scope of the invention as claimed.

100. . . Wireless communication system

110. . . Base station

120(1)-120(Z). . . Mobile device

130(1)-130(N). . . antenna

140(1)-140(M). . . antenna

210. . . message

220. . . Message generator

230. . . Cyclic redundancy check encoder

235. . . Cyclic redundancy check mask

240. . . Cyclotron encoder

250. . . Transmitter

260(1)-260(6). . . Bit delay

270(1)-270(3). . . Time point

280(1)-280(3). . . Encoding path

310(1)-310(32), 360. . . Butterfly illustration

320‧‧‧ possible path

330‧‧‧ Forward processing

340‧‧‧Retrospective processing

350, 900b‧‧‧ Code character selection procedure

900a‧‧‧ Viterbi forward processing and parallel traceability procedures

500, 700, 710, 720, 730 ‧ ‧ trace processing stage

510-540‧‧‧End status

550, 560‧‧‧ starting status

600‧‧‧ Forward processing stage

820‧‧‧transmitter

830‧‧‧ Receiver

840‧‧‧ Controller

850‧‧‧ memory

910-980‧‧‧ Process steps

FIG. 1 is a block diagram showing an example of a wireless communication system including a base station and a mobile device.

FIG. 2 is a block diagram showing an example of a Viterbi and cyclic redundancy check coding procedure according to the present invention.

Figure 3 (A) shows an example of a format structure diagram containing path and branch metrics.

Figure 3 (B) is an enlarged view of a portion of the format structure diagram of Figure 3 (A).

Figure 4 is an example of a block diagram showing the direction and traceability procedure in accordance with the present invention.

Figure 5 is an example of a format chart illustrating the traceability procedure in accordance with the present invention.

Figure 6 is an example of a format structure diagram illustrating the bit forced technique in accordance with the present invention.

Figure 7(A) is a diagram showing an example of a format structure diagram in accordance with the present invention to illustrate how to trace the least reliable decision during forward processing.

Figure 7(B) is a diagram showing an example of a format structure diagram in accordance with the present invention for explaining how to convert a format structure state at a least reliable decision node.

Figure 8 is a block diagram showing a wireless communication device for Viterbi and code character selection methods.

9(A) and 9(B) are diagrams showing an example of a flow chart of a Viterbi and cyclic redundancy check decoding program according to the present invention.

310(1)-310(32), 360. . . Butterfly illustration

320. . . Possible path

330. . . Forward processing

340. . . Retrospective processing

350, 900b. . . Select code character program

900a. . . Viterbi forward processing and parallel traceability procedures

Claims (17)

A decoding method for decoding a data received by a communication device, the data comprising a message encoded by a tail-biting convolutional code, the decoding method comprising the steps of: detecting the data to Finding a coded block having a specific data length; performing one or more forward processing iterations on the coded block to generate information representing a state diagram and identifying the plurality of end states in the state map to at most a plurality of paths in the initial state, and tracking one or more locations in the state map corresponding to one or more least reliable state transition decisions, wherein the information representing the state map corresponds to an encoder encoding the message a plurality of state transitions that may be generated; for the state diagram, a single parallel traceback operation is performed from the plurality of end states along the identified plurality of paths to determine when at least one of the particular paths of the state map The end state corresponds to a start state; when the single parallel traceback operation finds that an initial state coincides with a corresponding one end state, a Or a plurality of first candidate coded characters; generating one or more of the one or more least reliable state transition decisions by inverting one or more of the one or more of the state diagrams during the single parallel traceback operation Two candidate coded characters; identifying one or more correctly encoded characters from the one or more first candidate coded characters; and generating the message based on the one or more correctly encoded characters. The decoding method of claim 1, wherein the message is further subjected to a cyclic redundancy check code, and the step of identifying the correct code character comprises: when a first candidate code character passes through a loop Redundancy check condition Identify one or more correct coded characters. The decoding method of claim 2, wherein the step of recognizing the correct coded character comprises: identifying a one or more correct coded characters when the first candidate coded character passes the cyclic redundancy check condition , wherein the cyclic redundancy check code uses one of a plurality of known cyclic redundancy check masks. The decoding method of claim 1, further comprising the step of: calculating a quality metric for each of the first candidate coded characters of the one or more first candidate coded characters. Referred to as QM); wherein the step of identifying the correct coded character comprises: selecting the one or more correct coded characters based on the one or more quality metrics. The decoding method of claim 4, wherein the step of calculating the quality metric for each of the first candidate coded characters comprises performing the following calculation: QM = (PM _STATE - PM _MIN ) / (PM _MAX - PM _MIN ), where PM _STATE , PM _MIN , and PM _MAX represent path metrics in different states. The decoding method of claim 1, further comprising: calculating a quality metric for each of the one or more second candidate coded characters; wherein the correct coded word is recognized The step of encoding includes selecting the one or more correct encoding characters from the one or more second candidate encoding characters based on the one or more quality metrics. The decoding method of claim 1, wherein the data includes a known bit information, and the forward processing iteration further comprises: forcing a state transition in the state diagram to conform to the known bit information. The decoding method of claim 1, wherein the data includes a known bit information, and the decoding method further comprises the step of: during the single parallel traceback operation, excluding individual states that do not conform to the corresponding One or more first candidate coded characters of one or more states of the bit information are known. A communication device comprising: a receiver for receiving a data, the data comprising a message encoded by a tail-to-tail code; and a controller coupled to the receiver for detecting the data, Finding a coded block having a specific data length; performing one or more forward processing iterations on the coded block to generate information representing a state diagram and identifying the end state from the plurality of end states to a plurality of paths of a plurality of initial states, and tracking one or more locations of the state map corresponding to one or more least reliable state transition decisions, wherein the information representative of the state map corresponds to an encoder encoding a plurality of state transitions that may be generated by the message; for the state diagram, a single parallel traceback operation is performed from the plurality of end states along the identified plurality of paths to determine when at least one of the particular paths in the state map is An end state coincides with an initial state; Generating one or more first candidate coded characters when the single parallel traceback operation finds that an initial state coincides with a corresponding one of the end states; during the single parallel traceback operation, by inverting the state diagram One or more of the one or more least reliable state transition decisions, generating one or more second candidate coded characters; identifying one or more from the one or more first candidate coded characters Correctly encoding the character; and generating the message based on the one or more correctly encoded characters. The communication device of claim 9, wherein the message is further subjected to a cyclic redundancy check code, and the controller recognizes when a first candidate code character passes a cyclic redundancy check condition. The one or more correctly encoded characters. The communication device of claim 9, wherein the controller is further configured to: calculate a quality metric for each of the one or more first candidate coded characters; And selecting the one or more correct encoding characters based on the one or more quality metrics. The communication device of claim 11, wherein the controller calculates the quality metric for a first candidate code character using the following equation: QM = (PM _STATE - PM _MIN ) / (PM _MAX - PM _MIN ), where PM _STATE , PM _MIN , and PM _MAX represent path metrics in different states. The communication device of claim 9, wherein the communication device The controller is further configured to: calculate a quality metric for each of the one or more second candidate coded characters; and derive the quality metric from the one or more quality metrics The one or more correctly encoded characters are selected from the plurality of second candidate coded characters. The communication device of claim 9, wherein the data includes a known bit information, and the controller is further configured to force the state transition in the state table to conform to the known bit information. The communication device of claim 9, wherein the data includes a known bit information, and the controller is further used for the single parallel traceback operation, excluding individual states that do not conform to the corresponding One or more first candidate coded characters of one or more states of the bit information. A processor readable storage medium, wherein when the stored instructions are executed by a processor, the processor is configured to: receive a data, the data includes a message encoded by a tail-to-tail code; and detect the data to Finding a coded block having a specific data length; performing one or more forward processing iterations on the coded block to generate information representing a state diagram and identifying the plurality of end states in the state map to at most a plurality of paths of the initial state, and tracking one or more locations of the state map corresponding to one or more least reliable state transition decisions, wherein the information representative of the state map corresponds to an encoder encoding a plurality of state transitions that may occur during a message; For the state diagram, a single parallel traceback operation is performed from the plurality of end states along the identified plurality of paths to determine when at least one of the end states of the state map corresponds to a start state; The single parallel traceback operation finds that an initial state coincides with a corresponding one of the end states, and generates one or more first candidate coded characters; during the single parallel traceback operation, by inverting one of the state diagrams And the one or more least reliable state transition decisions, generating one or more second candidate coded characters; identifying one or more correct coded characters from the one or more first candidate coded characters And generating the message based on the one or more correctly encoded characters. The processor of claim 16, wherein the processor is readable by a storage medium, wherein the message is subjected to a cyclic redundancy check code, and the plurality of instructions for the processor to recognize the correct coded character include an instruction. The one or more correct coded characters are identified when the processor passes a cyclic redundancy check condition on a first candidate coded character.