Receiver receiving a signal including physical layer frames, and including a convolutional deinterleaver and a deinterleaver selector

A receiver receives a signal including an interleaved symbol stream. The receiver includes a convolutional deinterleaver including a plurality of delay portions each of which is arranged to delay symbols from the symbol stream from an input to an output by a different amount, the delay portions being arranged in a sequence. An input selector inputs the symbols from the symbol stream to the delay portions so that successive symbols are input in accordance with the sequence of the delay portions. An output selector configured to read the symbols from the delay portions by successively selecting the symbols from the outputs of the delay portions in accordance with the sequence of the delay portions to form a deinterleaved symbol stream.

FIELD OF THE DISCLOSURE

The present disclosure relates to receivers and methods for receiving signals that comprise an interleaved symbol stream.

BACKGROUND OF THE DISCLOSURE

In digital communication systems reliable communication of data is important and a number of methods exist to improve the reliability, for example, error correction coding and data interleaving. Error correction coding allows errors in received data to be reliably corrected dependent on a number of errors in a code word being below a certain threshold. However, in the event of burst errors this threshold can be exceeded and the error correction code may fail to reliably correct the errors in the data. Interleaving of symbols and frames in a communication system assists in distributing burst errors between code words, therefore reducing the possibility that the error threshold of the error correction code will be exceeded. However, although interleaving is an important tool in modern communication systems, the benefits of interleaving often come at the cost of increased complexity and memory requirements at both a transmitter and a receiver.

SUMMARY OF THE DISCLOSURE

According to the present invention there is provided a receiver for receiving a signal comprising an interleaved symbol stream. The receiver comprises a convolutional deinterleaver comprising a plurality of delay portions each of which is arranged to delay symbols from the symbol stream from an input to an output by a different amount, the delay portions being arranged in a sequence. An input selector is configured to input the symbols from the symbol stream to the delay portions so that successive symbols are input in accordance with the sequence of the delay portions. An output selector is configured to read the symbols from the delay portions by successively selecting the symbols from the outputs of the delay portions in accordance with the sequence of the delay portions to form a deinterleaved symbol stream. A controller is configured to detect a discontinuity puncture in the interleaved symbol stream resulting from symbols being punctured from the interleaved symbol stream, and to identify symbols in the interleaved symbol stream affected by the discontinuity puncture, the identified symbols in the interleaved symbol stream being symbols which would be out of sequence in the deinterleaved symbol stream as a result of the discontinuity puncture. The controller is also configured to store the identified symbols, and to input the identified symbols into the delay portions to compensate for the discontinuity, wherein at least one of the delay portions is formed from one or more memories and at least one of the identified symbols is stored in the one or more memories of the delay portions, which would have been occupied by the symbols which had been punctured from the interleaved symbol stream.

The introduction of discontinuity punctures into an interleaved symbol stream and the detection of discontinuity punctures at the deinterleaver enable discontinuities such as interleaving frame transitions to be incorporated into convolutional interleaving without transmitting dummy symbols to ensure that symbols from consecutive interleaving frames are not interleaved. The identification of symbols affected by discontinuity punctures allows the correct deinterleaved stream to be output by the deinterleaver even though symbols have been punctured from the interleaved stream. In order to achieve the correct deinterleaved symbol stream whilst reducing the impact on latency through the interleaver, identified symbols are buffered or stored and then later read back into the delay portions of the deinterleaver to compensate for the discontinuity punctures. The present invention reduces memory requirements compared to using a single dedicated buffer for all stored symbols as it uses delay portion memory which is unoccupied due to the puncturing to store one or more of the identified symbols. This arrangement allows a deinterleaver to be reconfigured and interleaving frame lengths changed whilst maintaining a constant latency through the deinterleaver. The arrangement also utilises less memory than either than a block interleaver or a convolutional interleaver with a dedicated buffer to store all the identified symbols.

Various aspects and features of the present invention are defined in the appended claims and include claims to a method of receiving a signal comprising an interleaved symbol stream, a computer program for receiving a signal comprising an interleaved symbol stream, and a data processing apparatus for processing a signal comprising an interleaved symbol stream.

DESCRIPTION OF EXAMPLE EMBODIMENTS

FIG. 1provides a block diagram of a simplified digital communication network100. A network as illustrated byFIG. 1may operate in accordance with any known communication standard such as the proposed Advanced Televisions Systems Committee 3 (ATSC3.0) standard or DVB-T standard for example. A core network101transmits a signal, such as a digital audio-visual signal representing television content, to a transmitter102that transmits the signal. The transmitted signal is received by the receivers103, which in the case of a digital audio-visual signal may be a television set with a display, a receiver within a television set, a television receiver device or any other compatible device such as for example a mobile terminal (such as a cellular telephone) including or connectable to a television receiver device. The receiver is operable to receive the transmitted signal and provide the content represented by the signal to a display. AlthoughFIG. 1shows the wireless transmission of a signal, the transmission of the signal may take place over cables in a cabled communication system such as those that operate in accordance with ATSC Cable or DVB-C.

FIG. 2shows a block diagram of example data processing elements which may form part of a transmitter chain of the core network101and the transmitter102ofFIG. 1. InFIG. 2, the data source201generates data to be transmitted by the transmitter102. The data source201feeds the data (possibly via intermediate elements) to a forward error correction (FEC)202encoder which performs error correction encoding of the data. The output of the forward error correction (FEC) encoder202may then be processed by other blocks, for example a constellation mapper203, which maps groups of bits onto a constellation point, and is to be used for the conveying the encoded data bits. The outputs from the constellation mapper203are constellation points represented by real and imaginary components. The constellation points represent symbols formed from two or more bits depending on the modulation scheme used, which may be, for example, QPSK, QAM, 16QAM etc. The stream of symbols is then input to an interleaver204which may interleave the symbols across time and/or frequency. The interleaver204interleaves input symbols such that the symbols are distributed across one or more FEC code words, thereby creating a more uniform distribution of errors in cases where errors may occur in bursts in time or frequency. The interleaved symbols are received by a frame builder205, which may form these symbols and symbols from other sources, which are used to convey information about the format of the transmission, into a set of symbols which will be referred to as a physical layer frame. However, in some examples the stream of symbols may have already been divided into frames or symbols allocated to frames prior to interleaving. A frame may then be processed by further blocks which modulate the frame onto for example a set of OFDM symbols, which are then used to modulate an RF signal for transmission over a radio channel or a cable channel. AlthoughFIG. 2depicts five elements, the core network101and transmitter102may also comprise a number of other elements common to the transmission of a digital signal, such as a multiplexer, a compression coder and signal amplifiers etc.

FIG. 3provides a block diagram of example data processing elements that may be comprised by the receivers103where the receivers103are operable to receive the signal transmitted by the transmitter102shown inFIGS. 1 and 2. The transmitted signal comprising the symbols are received by a frame decoder301via a suitable antenna and demodulation elements. The frame decoder301demultiplexes the frame and outputs a stream of interleaved symbols. These symbols are passed to a deinterleaver302which reverses the interleaving performed by the interleaver204. The output of the deinterleaver then may pass through a demapper303, which converts the symbols to a stream of bits. The data then passes to a FEC decoder304which attempts to correct any errors in the data.FIG. 3illustrates a number of elements which may be found in a receiver such as those pictured inFIG. 1, however, the receiver103may also comprise a number of intermediate blocks not shown inFIG. 3such as a demodulator, signal amplifier and other data processing elements common to digital receivers such as those required to provide audio-visual content to a display device.

Interleaving is often used in digital communication systems to improve the performance of forward error correcting codes. In many communication channels, errors often occur in bursts rather than in isolation or independently. If the number of errors within a code word exceeds the error-correcting code's capability, the error correction process may fail to recover the original code word. Interleaving ameliorates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution of errors. These code words are generally transmitted sequentially in time; hence the name “time-interleaving” because this stream of symbols is then interleaved in time. However, interleaving may also be done in the frequency domain so that in OFDM systems symbols may be distributed across different frequencies.

One method of performing interleaving is called block interleaving. This is used to implement the time-interleaving in many digital communication systems, for example DVB-T2 and ISDB-T. In a block interleaver blocks of symbols are interleaved and these blocks may be referred to as interleaving-frames. Another method of performing interleaving is convolutional interleaving. Convolutional interleaving is also known and used in digital communication systems, for example DVB-T. The advantage of a convolutional interleaver is that it generally uses half the amount of memory that is required for block interleaving, whilst giving similar performance. There are, however, disadvantages of convolutional interleaving when compared to block interleaving. For example, the data to be interleaved is continuous, rather than being naturally divided into discrete interleaving frames. This means that it may not be possible to change the interleaver parameters whilst the interleaver or deinterleaver is running. Secondly, a size of a convolutional interleaver needs to be related to other parameters of the communication system in which it is operating so the deinterleaver at the receiver can be synchronised with the interleaver at the transmitter.

FIG. 4illustrates the internal operation of a convolutional interleaver, such as the interleaver204depicted inFIG. 2, that would typically be found In the transmitter side of a digital communication system as depicted inFIG. 1.FIG. 4also illustrates the internal operation of a convolutional deinterleaver, such as the deinterleaver302depicted inFIG. 3, that would typically be found In the receiver side of a digital communication system as depicted inFIG. 1. The interleaver204and the deinterleaver302each comprise an input selector401, an output selector402and a plurality of delay portions403, where the delay portions may also be referred to as interleaver/deinterleaver rows due to their layout in the interleaver and deinterleaver visualisations. The input selector401is operable to input symbols into a delay portion and the output selector402is operable to read out symbols from the delay portions. In some examples the input and output selectors401,402may be synchronised such that they input and read out symbols from a same delay portion, however, they may also be unsynchronised such that they input and read out symbols from different delay portions. The selectors401,402may for example become unsynchronised in the interleaver when output selector402does not read out a symbol from a delay portion but the input selector401continues to input a symbol to said delay portion.

The plurality of delay portions403are arranged to delay symbols by different amounts from when a symbol is input into a selected delay portion by the input selector201and read out from the selected delay portion by the output selector402. At least one of the delay portions is made up of one or more memories or memory elements404where the delay introduced by a delay portion is partially dependent upon the number of memory elements the delay portion comprises. The number of symbols a delay portion is operable to store or delay at any one time is dependent on the number of memory elements the delay element comprises. In some examples the arrangement of the memory elements404may be said to form columns which are analogous to the interleaver/deinterleaver rows mentioned above. Each memory element may be associated with a memory location in an interleaver/deinterleaver memory which is operable to store a symbol input into a delay portion. The delay portions403are arranged in a sequence such as that illustrated inFIG. 4, where the delay portions403in the interleaver204are arranged in an order corresponding to decreasing delay i.e. decreasing number memory elements, and the delay portions403in the deinterleaver302are arranged corresponding to increasing delay i.e. increasing number of memory elements. However, the sequence of delay portions403may be arranged in any sequence depending upon the interleaving pattern or sequence required. The input selector204is configured to input symbols from an input sequence in accordance with the sequence of the delay portions403as shown by the dashed line405. Likewise, the output selector402is configured to read symbols from the delay portions in accordance with the sequence of the delay portions403as shown by the dashed lines406to form a deinterleaved symbol stream.

The input to the convolutional interleaver204may be a stream of bits, symbols, blocks of bits or symbols etc. The term symbol used throughout this description includes all these cases. Each symbol from a symbol stream is input by an input selector401, the selectors advance one delay portion downwards after the input of a symbol, wrapping round back to the top after the bottom delay portion. Each time a symbol is read out of or input to a delay portion403symbols remaining in the delay portions403are shifted towards the output selector402by one or more memory elements such that at least the memory element nearest to the input selector becomes vacant i.e. no longer contains useful data. During normal operation the next symbol from the interleaved or uninterleaved stream of symbols is input into the vacant memory element by the input selector401. In the case of the delay portion which does not comprise any memory elements404, the symbol input by the input selector401is immediately output or read out by the selector402before the selectors advance one delay portion downwards. Consequently, the delay between the input of a symbol from the stream of symbols into a delay portion and the output or reading-out of the same symbol from the delay portion is dependent upon the number of memory elements404in the delay portion and the frequency that symbols are input or read out from the delay portion403. Although in the description above the selectors401,402move in a downward direction, they may also move in an upwards direction after the input and reading-out of symbols from each delay portion403. In some circumstances a symbol may be output, without the use of the output selector, from a delay portion in response to the input of a symbol to the delay portion by the input selector401and is not read directly into the interleaved/deinterleaved symbol stream. As can be seen inFIG. 4, as a result of the different delays introduced by the delay portions403of the interleaver204, the stream of symbols input into the interleaver204or deinterleaver302will be read-out in a different interleaved or deinterleaved order, respectively, which is dependent on the number of delay portions, the delay introduced by each delay portion, and the sequence of the delay portions. As can also be seen inFIG. 4, the deinterleaver302has a structure that corresponds to that of the interleaver204such that the interleaved symbols inputted into the deinterleaver are read-out in the uninterleaved order of the stream of symbols that were input into the interleaver at the transmitter. Although inFIG. 4the interleaver204and the deinterleaver302are illustrated as comprising rows and columns of memory elements, convolutional interleaving may also be represented via other visualisation. For example, they may be represented via the use of matrices where the size of a matrix and its elements determine the delay and therefore the interleaving/deinterleaving of the input/output symbol stream. Furthermore, the elements of the interleaver and deinterleaver described above and throughout the application may be implemented on a multipurpose or dedicated processor chip, where the functionality of the interleaver and deinterleaver is equivalent to that described but the implementation differs from the visualisations that are illustrated and described. For instance, the delaying of symbols and the input and output of symbols may be performed via memory address manipulation as opposed to the physical transfer of data representing symbols between memory elements and locations.

In some digital communications systems it may be necessary to reconfigure the interleaving/deinterleaving process from time to time. If a block interleaver and deinterleaver is used, then this is straightforward, because each interleaving frame is discrete so the reconfiguration can be done in between interleaving frames. In order to reconfigure a convolutional interleaver or deinterleaver however, it may necessary to shut down them down so they either contain no data or contain data from only a single interleaving frame. In some other systems it may be desirable to shut the time-interleaver down at regular intervals, for instance, after every interleaving frame. If the interleaving/deinterleaving process is shut down, then either symbols would remain in the interleaver204and deinterleaver302delay portions403and memory elements404, or some method is required to overcome the fact that some delay portions403in the interleaver204and deinterleaver302would contain symbols whilst others did not. It can also be seen that when restarting a interleaving/deinterleaving process after shutting down and reconfiguring the process, then either data that remained in the interleaver and deinterleaver delay portions and memories prior to shutting down would be lost or some method is required to overcome the fact that some delay portions in the interleaver and deinterleaver would contain symbols whilst others did not. Losing data will often be unacceptable and therefore a method is required to overcome the fact that some delay portions in the interleaver and deinterleaver would contain symbols whilst others do not.

A first technique to overcome the fact that some delay portions in the interleaver204and deinterleaver302would contain symbols whilst others do not is to insert dummy symbols into the interleaver whilst continuing the interleaving/deinterleaving process until all the real data has passed through both the interleaver204and deinterleaver302. A disadvantage to this approach is that bandwidth across the communications channel is wasted by transmitting these dummy symbols.

A second technique to overcome the fact that some delay portions in the interleaver204and deinterleaver302would contain symbols whilst others do not, is for a controller within the interleaver or deinterleaver to configure the selectors401,402to skip over delay portions which contain no valid symbols during current iteration so that either a symbol is not read out from, or a symbol is not input to a delay portion during the iteration. This skipping may result in symbols that are out of sequence in the interleaved or deinterleaved stream of symbols being punctured from the interleaved symbol stream and transmitted at a later time. Alternatively, it may be viewed that dummy symbols have been introduced and it is these that are punctured from the interleaved symbol stream but are not transmitted at a later time. In either case, bandwidth across the communications channel is not wasted because no dummy symbols are transmitted through it and data symbols are only delayed. If the selectors401,402skip over delay portions in response to symbol punctures or to puncture symbols from the transmitted stream, it is necessary for the interleaver204and deinterleaver302to be able to determine when it is necessary to do this. One method of doing this is for the interleaver204and deinterleaver302to store a flag to indicate whether each memory element404and its associated memory location contains valid or invalid data. A possible disadvantage of this is that extra memory is required to store this flag, which is a particular disadvantage in the receiver in a broadcast system because there will be many more receivers than transmitters and therefore the accumulated extra memory may be significant. An alternative method in accordance with the present disclosure is for the controller(s) to be able to calculate and detect when it is necessary for the selectors401,402to skip over delay portions which contain no valid symbols or when there is no symbol which should be input into the delay portion at that time or iteration. For example, the controller may be configured to detect when a discontinuity puncture results from a discontinuity in the interleaved symbols or a discontinuity in the symbols to be interleaved. After detection the controller can then identify symbols in the interleaved or deinterleaved symbol stream which are affected by the discontinuity or discontinuity puncture. The aforementioned discontinuities will normally arise from a transition between frames in the uninterleaved input symbol stream or when the interleaver and deinterleaver and required to be reconfigured and therefore the symbol stream separated into interleaving frames where symbols are not interleaved across the frames. The points at which the interleaver204or deinterleaver302skip whilst shutting down the interleaving/deinterleaving process i.e. just before a discontinuity such as a interleaving frame transition, will be referred to as shutdown punctures; the points at which the interleaver or deinterleaver skips whilst starting up the interleaving/deinterleaving process i.e. after a discontinuity such as a interleaving frame transition, will be referred to as startup punctures. Shutdown punctures may occur when a symbol stream is divided into interleaving frames and a symbol is not transmitted because it forms part of the next interleaving frame and it is required that all symbols from the current interleaving frame are transmitted prior to the transmission of the next interleaving frame. Similarly, a startup puncture may occur when two successive interleaving frames are transmitted separately i.e. not interleaved between each other, and the symbols in the interleaved stream that would belong to the preceding interleaving frame are not transmitted interleaved with the symbols from the subsequent interleaving frame. As mentioned above, punctured symbols are punctured from their normal position in the interleaved symbol stream and transmitted at a subsequent time. Consequently, even with puncturing, symbols are transmitted at the same rate and with the same latency but in an amended order to ensure separation between the symbols of two successive interleaving frames. It is the role of the controller in the interleaver to ensure the correct symbols are punctured to account for a discontinuity and the effects of the puncturing compensated for i.e. transmit at a later time those symbols which do not belong to the current interleaving frame. Correspondingly, it is the role of the controller in the deinterleaver to take account of or compensate for the amended order of transmission of the symbols when reconstructing the uninterleaved symbol stream.

Referring again toFIG. 4, in order to calculate when a delay portion403should be skipped over it is necessary to number the delay portions403sequentially and number the iterations of the selectors401,402through the sequence of delay portions in the following manner
Npor=0,1,2 . . .Npors−1
Niter=0,1,2 . . . ∞
where Nporsis the total number of delay portions403in the interleaver204or deinterleaver302and the number of symbols from the stream of symbols left in the current interleaving frame is Nframe.

Using the variables defined above it is possible to calculate a reference number, also known as the ordinal number, for each input and output symbol and/or each memory element404of the interleaver204or deinterleaver302relative to the time that the startup process began and the place of the symbol in the uninterleaved stream. When the selectors move in a downwards direction relative to the delay portions as shown in the Figures, the reference number may be given by
Nref=(Niter−Npors+1)Npors+(Npors+1)Npor.

The reference number is the position of the symbol in the uninterleaved symbol stream i.e. the position of symbol in the stream before interleaving or after deinterleaving, or the position of the symbol in a stream if it were stored in a particular memory element in the deinterleaver302or interleaver204. Consequently, if a reference number is less than 0, then a startup puncture discontinuity has been detected because the symbol would belong to the preceding interleaving frame and the relevant selector(s)401,402should move on to the next delay portion:
Nref<0

If the reference number is greater than or equal to Nframethen a shutdown puncture discontinuity has been detected because the symbol would belong to the subsequent interleaving frame and the relevant selector(s)401,402should move on to the next delay portion:
Nref≥Nframe

In this way startup and shutdown punctures can be detected without having to store a flag for each memory location or element in order to indicate whether the symbol and or memory element is valid or invalid. In some examples the symbols and/or the memory elements may be allocated reference numbers and a discontinuity detected and compensation introduced when the reference numbers do not correspond to each other. In other examples the reference numbers of symbols may be compared to what should be expected during the current iteration and compensation introduced in the form of skipping the input or output of symbol from a delay portion(s) when a discrepancy between the reference numbers is detected. In yet another example, symbols affected by a discontinuity or puncture may be identified via a comparison between their reference number or the reference number of the memory element they are associated with, and those of other symbols in the uninterleaved or interleaved symbol stream. For instance, via a comparison between a symbol's reference number and the reference number of a symbol expected to be associated with a particular memory element in a selected delay portion.

In examples where the memory elements are allocated reference numbers, if the reference number associated with a memory element from which a symbol is to be read from or input to is either Nref<0 or Nref≥Nframe, then a puncture will have been detected. Compensation is then introduced in the form of skipping the input or skipping the output of a symbol to or from the delay portion(s) in which the memory element is located. For instance, if a memory element in the deinterleaver has a reference number of 78 associated with it but the interleaving frame has only 70 symbols remaining, the next symbol in the interleaved symbol stream will not be input into the memory element because the selector will skip over the delay portion containing the memory element.

Whilst the interleaver204or deinterleaver302is running, a count of the number of symbols output from the interleaver204or deinterleaver302can be maintained. Once this is equal to
Nframe−1
then all the symbols of the current frame have been output.

Similarly, if the selectors401,402move in the opposite direction i.e. an upwards direction relative to the delay portions in the Figures, a similar expression for Nrefcan be found:
Nref=(Niter−Npor)Npors+Npor
where the same expressions for detecting startup and shutdown punctures can be used.

In reality, we may wish to run the interleaver204or deinterleaver302for a long time, having started it before the time that it would be shut down was known. The technique described above can be used for this situation in order to detect the startup punctures, because it is not necessary to know the length of the interleaving frame Nframein order to detect startup punctures. However, the above technique needs to be adapted to enable shutdown punctures to be detected, given that the length of the interleaving frame Nframeis not known. In this situation, we define some arbitrary time before the shutdown process has started and at which the selectors are at portion0(Npor=0). We define Niterto be 0 at this time and we define Nframeto be the number of symbols remaining in the interleaving frame. Then the method described above can be used to detect the shutdown punctures.

As already stated, in some examples it may be necessary for the selectors in the interleaver204and the deinterleaver302to be synchronised. If the interleaver204has been started before the receiver103was switched on, then the receiver103needs to know the correct position of the selectors401,402. This may be achieved by the transmitter signalling the position of the selectors401,402at the start of each frame in some form of selector synchronisation data or signalling that appertains to that frame. Then, during its acquisition process, the receiver103can decode that signalling in order to set the selector401,402in the correct position. Once the deinterleaver302is synchronised with the interleaver204, then this signalling does not need to be decoded.

It is also likely the receiver103needs to be able to synchronise to the output of the deinterleaver302. For example, if the symbol stream were divided into FEC-frames for error correction purposes, the receiver103would need to be able to determine the position of the start of one of those FEC-frames. This may be done by the transmitter102signalling the number of symbols that the deinterleaver302will output during that frame before some known reference point, for example the start of a FEC-frame, will be output from the deinterleaver302.

It may be desirable that the latency of a communications system100is constant. For example, in a broadcast system, the original video or audio signal will be a continuous stream which needs to be output or displayed as such by a receiver103. When the selectors401,402of the interleaver204or deinterleaver302skip a delay portion403and therefore do not input and or read out symbols from a delay portion, other symbols will be affected and the rate of symbols input and output will be affected. Consequently the latency through the system may be affected because a symbol expected to be in the symbol stream has been punctured from the stream in order to be transmitted at a later time. Therefore, in many communications systems buffering of symbol(s) affected by a discontinuity puncture will be required in order to keep the latency constant and compensate for the effects of the discontinuity puncture.

In the interleaver204, if a shutdown puncture is determined then the current symbol may not be read out by the output selector402and the current delay portion skipped so that the current symbol is not read out into the interleaved symbol stream. However, there will be data that is required to be input to the current delay portion. Therefore, the current symbol may be outputted in an alternative manner and stored somehow in a buffer. Likewise, in the deinterleaver302, if a shutdown puncture is determined, then the current symbol from the interleaved symbol stream will not be input to the current delay portion and so this input data is required to be stored somehow in a buffer. This is particularly important because in many communications systems, and particularly a broadcast system, the input data will be a continuous, unstoppable stream and therefore symbols will either have to be stored or transmitted. In some examples the input symbols in the interleaver may be required to be stored depending on the input and reading out processes, and likewise in some examples the output symbols from the deinterleaver may be required to be stored depending on the input and reading out processes.

FIG. 5shows the deinterleaver302shortly before a shutdown puncture will occur. The symbol in each memory element404are numbered to indicate their reference number in the uninterleaved stream. Consequently, the controller in the deinterleaver identifies the symbols which would be affected by the puncture where the puncture has been determined by using the expressions given above and the location of the memory elements that the symbols would be input into. For example, the controller may identify symbols whose reference number would be out of sequence in the uninterleaved symbol stream if they were to be read out as normal. Alternatively, the controller may identify a memory element and delay portion where a punctured symbols would normally have been input and skip the inputting of a symbol to the identified delay portion. This may be because the reference number of the memory element exceeds Nframeand the symbol originally destined for this memory element will be received at a later time due to a shut down puncture at the interleaver. InFIG. 5, the symbol with index0in the second delay portion is the first symbol after the position of the shutdown was signalled and the symbol with index X in the last or bottom delay portion is a symbol before that position. The next symbol in the input stream in this case also has the index X and so this needs to be output before the symbol with index0.

FIG. 6shows the deinterleaver302one symbol later as a shutdown puncture occurs. It can be seen that the bottom delay portion needs to be shifted in order for the last symbol in the bottom delay portion to be read out because symbol X needs to be output before the symbol with reference number0, otherwise the output stream will be different to the uninterleaved stream (because the symbol reference numbers will not be sequential). However, it can also be seen that the next input symbol (which also has the index X) should not be input to the bottom delay portion of the deinterleaver because the symbol which would have been intended for this delay portion has been punctured from the interleaved symbol stream and will be transmitted at a later point in time. If the next input symbol from the symbol stream were input into the bottom delay portion it will be output after the symbol with reference0and so the output stream will be different to the uninterleaved stream (because the symbol reference numbers will not be sequential). Therefore, because the input stream is continuous and unstoppable, the next input symbol needs to be stored somehow.

FIG. 7illustrates a method of storing the symbol from the interleaved stream which has not been input into a delay portion, where a buffer701is used at the input to the deinterleaver302. The buffer701is represented by the new memory at the input, which contains the symbol X. As each shutdown puncture occurs the number of symbols stored in the buffer701increases. A possible disadvantage of this method is that extra memory is required to implement the buffer701. This may be a particular disadvantage in the receiver103in a broadcast system because there will be many more receivers than transmitters or a in transceiver in a two-way communication system. In order to reduce the impact of this disadvantage, it is advantageous to limit the amount of memory required to implement this input buffer701.

A technique in accordance with an example of the present disclosure is to limit the amount of memory required to implement the input buffer701is to reuse the deinterleaver memory elements404to implement the buffer701. Referring again toFIG. 7, it can be seen that a memory element702in the bottom delay portion becomes free as the shutdown puncture occurs. Furthermore, it turns out that no more symbols will be input to the bottom delay portion during the current interleaving frame and so the leftmost memory element in the bottom delay portion is no longer required during this interleaving frame. This can be shown by considering the expression for the reference number Nreffor the deinterleaver302with the selectors401,402moving in a downward direction:
Nref=(Niter−Npors+1)Npors+(Npors+1)Npor

The shutdown puncture is determined because the reference number Nrefof the symbol which would be stored in the vacant memory element702had a puncture not occurred is greater than the (remaining) length of the interleaving frame Nframe, or equivalently, the reference number associated the memory element702is greater than the (remaining) length of the interleaving frame. It can be seen that for a fixed Npor(e.g. the bottom delay portion in this case) and a fixed Npors, on the next iteration Niterwill have increased by 1 and so the value of Nrefwill necessarily be greater than on the current iteration. The shutdown puncture is determined because the reference number Nrefis greater than the (remaining) length of the interleaving frame Nframe, consequently, a shutdown puncture will necessarily be determined for this delay portion on the next iteration and all subsequent iterations (because Niteralways increases). It can also be seen that whenever a shutdown puncture is determined (thus requiring an input to a delay portion to be skipped), a memory element and corresponding memory location becomes no longer required.

Therefore, whenever a shutdown puncture is determined and a memory element404becomes unoccupied, the memory location associated with the unoccupied memory element can be used to implement a buffer701to store in input symbol that was not input into a particular delay portion.

FIG. 8shows the deinterleaver when the memory element702and its corresponding memory location have been moved to implement the buffer701.

FIG. 9illustrates the deinterleaver302when the next input symbol from the stream of interleaved symbols which has reference number7has been input. After reading out of the next symbol, the selector401will switch to the top delay portion of the deinterleaver302and so symbol X that was stored in the input buffer701will be read out immediately, which is what is required in order to recreate the uninterleaved stream correctly.

FIG. 10illustrates the deinterleaver after the next symbol has been input, which has the reference number15. This is stored in or written to the input buffer701, after the symbol7previously in the input buffer is written to the deinterleaver302in order to compensate for the previous discontinuity puncture. It can be seen that, based on the reference numbers, the uninterleaved sequential stream of symbols will be recreated by the deinterleaver when the symbols are read out. The effects of puncturing symbols at the interleaver and the skipping of delay portions are therefore compensated for.

FIG. 11shows the deinterleaver302after a next shutdown puncture such that another deinterleaver memory element and corresponding memory location are no longer required and become available to be used for implementing the input buffer701. As is evident fromFIG. 11, as each shutdown puncture occurs, a new memory element and its associated memory location is released from the deinterleaver302and the amount of memory required to implement the input buffer701increases by one memory location. Accordingly, the input buffer701can therefore be implemented using memory locations of memory elements404released from the deinterleaver302. Consequently, the process of detecting discontinuity punctures, identifying and storing symbols affected by the discontinuity puncture and subsequently inputting the stored symbols into the delay portions to compensate for the discontinuity punctures can be carried out by a controller with little or no additional memory for symbol storage.

The reuse of the interleaver memory for the input buffer701described above results in an advantage that no additional memory for the storing of symbols is required beyond that of the deinterleaver memory itself when discontinuity punctures occur. This is particular advantageous when considering receivers in a system due to their lower cost and higher numbers compared to transmitters. Consequently, as a result of the input buffer701being formed from the deinterleaver memory locations, the capacity of a digital communication system that involves interleaving can be maintained when there are discontinuities such as puncture discontinuities without increasing the memory requirement of the deinterleaver and hence the cost of the associated receiver. Furthermore, the performance and memory advantages of convolutional interleaving can be combined with the advantages of block/frame separation usually associated with block interleaving.

FIG. 12shows the deinterleaver302as the last shutdown puncture occurs in a scenario where all the memory locations have been reused in the input buffer701. By this time all the symbols in the input buffer701appertain to the next interleaving frame, where the next interleaving frame is the interleaving frame that followed the interleaving frame where the shutdown occurred. In order to enable the deinterleaving of the next frame the input buffer701and the symbols it stores may be reconfigured as another deinterleaver302such that the memory locations of the input buffer701are once again associated with memory elements404of the delay portions403.

FIG. 13illustrates the reconfiguration of the input buffer701into the deinterleaver302whilst simultaneously accounting for the startup punctures from the following interleaving frame. This may for example occur when the symbols from the current frame have been read out from the delay portions403and the stored symbols relate to the next frame. The reconfiguration comprises allocating the memory locations from the input buffer701right to left into the deinterleaver vertically from top to bottom, filling columns formed from memory elements from right to left. In some examples the process of reconfiguration may be considered to be inputting the stored symbols into the delay portions in accordance with the predefined sequence illustrated inFIG. 13. However, reconfiguration may also be achieved by reconfiguring memory mapping and the memory locations which are associated with each memory element and delay portion. The fact that this reconfiguration sequence may be predefined may reduce the computational burden on the controller when reconfiguration is required.

FIG. 14shows the deinterleaver302after the reconfiguration has been completed. The next symbol input will have reference number0and will be input and immediately read out of the top delay portion before symbol1in the second delay portion will be read. Consequently, it can be seen that the uninterleaved stream will be recreated.

FIG. 15illustrates the deinterleaver302in an example of a scenario when the following interleaving frame is shorter than the sum of number of memory locations in the interleaver plus the number of memory locations in the deinterleaver. In this case shutdown punctures may need to be accounted for in the reconfiguration process. For example, inFIG. 15symbol0should not be input into the bottom delay portion because it would be read out after symbol1and therefore the deinterleaved stream of symbols would be incorrect. The expressions given previously can be used to determine the occurrence of shutdown punctures during the reconfiguration process. In the case of the left most memory element in the bottom delay portion inFIG. 15, the reference number Nrefwill be greater than Nframeand therefore this memory location associated with the memory element must remain as an input buffer memory location.

Memory Management

It is likely that the memory for the deinterleaver302already described would be implemented as part of a random access memory rather than as discrete memory locations such as flip-flops. In that case, rather than physically moving data between memory locations in the random access memory, it would be better to move the data virtually by controlling the address mapping. In this case, the following memory mapping functions faand fiare required for the deinterleaver:
ARAM=fa(Npor,Ncolumn)
ARAM=fi(Nbuffer)
whereARAMis the address in the random access memoryNporis the delay portion numberNcolumnis the column numberNbufferis the position in the input buffer

The function fais commonly known in the art because convolutional interleaving/deinterleaving is a known technique and so techniques for implementing such interleavers and deinterleavers in a random access memory are also commonly known.

FIG. 16illustrates a deinterleaver302where the numbering from top to bottom of the delay portions403and the numbering of the columns from left to right is shown. A suitable memory mapping function for the deinterleaver302ofFIG. 16is given below, where the columns are numbered right to left from 0 to Ncolumns−1 and the delay portions are numbered top to bottom from 0 to Npors−1:

The function fi(Nbuffer) is dependent on the present application and so is not known in the art. The function fi(Nbuffer) also depends on the order in which memory locations become free (to be reused in the input buffer701) which in turn depends on the position of the shutdown punctures. The position of the shutdown punctures depends on the length of the interleaving frame (or the number of symbols left in the interleaving frame once the end of the interleaving frame has been signalled), Nframe, and the number of delay portions403in the deinterleaver, Npors. In order to simplify this relationship a restriction is placed on Nframe
NframemodNpors=0.

In other words, Nframemust be an integer multiple of Npors. With this restriction applied, the function fi(Nbuffer) becomes:

The function fi(Nbuffer) enables the random access memory address to be calculated for each memory location in the input buffer701. Function fi(Nbuffer) is complicated and so may be difficult to implement, particularly in hardware.

Due to the operation of the input buffer701random access to the locations within it is not required. Instead, some kind of pointer or pointers may be maintained, which point to the position in the input buffer701from which symbols should be read or to which symbols should be written. Instead of manipulating these pointers in the linear domain 0 . . . Nbuffer−1, the pointers can be manipulated in the domain 0 . . . Npors−1.

FIG. 17illustrates the order in which memory locations associated with memory elements404of the delay portions403become free. As long as the above restriction is adhered to, the manipulation of pointers in this domain is straight forward because the memory locations will become free in the order shown by the dashed line1701.

Each delay portion403in the deinterleaver302is effectively a shift register where a symbol is shifted out the last memory element404of each delay element403at each iteration. If the deinterleaver302is implemented using flip-flops for example, then implementation of a shift register is well-known. However, if the deinterleaver302is implemented using a random access memory it is convenient to implement each delay portion as a ring buffer. A ring buffer is a known technique in which a shift register is implemented using a fixed block of memory of the same length as the shift register. A pointer is then maintained and the shifting of the shift register is simulated by first reading the data pointed to (which becomes the output of the shift register i.e. the a delay portion), then writing data to the same location (which is the input data to the shift register i.e. delay portion) and then moving the pointer to point to the next memory location whilst wrapping round to the first memory location if the pointer should be incremented beyond the end of the block of memory.

FIG. 18illustrates a circular buffer1801. A pointer1802points to the memory location containing the symbol with index26and when the next symbol arrives the symbol with index26would be read from the memory location pointed to by the pointer1802. The new symbol would be written to that same memory location and then the pointer1802incremented so that it points to the memory location which contains the symbol with index27. Thus the next output from the circular buffer1801will be the symbol with index27and the symbol that was written to the memory location pointed to inFIG. 18would be output after five further read/write cycles. Thus, it can be seen that the circular buffer1801is implementing a shift register without data having to be physically shifted between memory locations. The pointer1802can be mapped to the linear random access memory address space using a function such as fa(Npor,Ncolumn) described above.

In some examples the input buffer701may be seen as a shift register that can expand or contract. The input buffer701is constructed using memory locations freed from the deinterleaver302and above it has been shown that the number of free memory locations available from the memory elements404of the deinterleaver302at any time is equal to the number required by the input buffer701. In examples where the deinterleaver302is implemented using flip-flops the implementation of a shift register that can expand or contract is straight forward and the shifting of the shift register is well-known and new flip-flops can be added or removed using suitable multiplexing logic.

In other examples, the deinterleaver302may be implemented using a random access memory. Whilst the implementation of a shift register that can contract is straightforward, the implementation of a shift register that can expand is difficult when using random access memory. As described above, a convenient method of implementing a shift register using random access memory is to use a circular buffer. However, circular buffers are generally implemented as a buffer of constant size: a problem may arise if the circular buffer is to be expanded if the pointer is not pointing to one end of the block of memory used to implement the circular buffer. If it was required to expand the circular buffer1801shown inFIG. 18and with the pointer1802in the position shown, a new memory location would be required between those containing symbols with indexes26and31. As the block of memory used to implement the circular buffer is continuous, this may is difficult. However, the block of memory used to implement the input buffer701in may not be physically continuous but instead may be constructed using memory locations freed from the deinterleaver302, consequently, the memory locations would be accessed using the methods described above, effectively making the memory locations continuous.

Another technique to implement the input buffer701would be to use a first-in first-out memory (FIFO) arrangement. A FIFO is a similar structure to a circular buffer except that two pointers need to be maintained, one for writing/input and one for reading/output. An advantage of using a FIFO rather than an expanding shift register is that a FIFO is effectively a shift register that can expand or contract as well as shift. However, implementing a FIFO requires a fixed amount of memory equal to its maximum size, whereas in this application this will not be the case if the memory used to implement the FIFO is that released from the deinterleaver when shutdown punctures are encountered.

Instead of using memory released from the deinterleaver302to implement the FIFO, another method of implementing a FIFO is to use a second block of memory. It was shown inFIG. 12above that the maximum size of the input buffer701is equal to the number of memory locations in the deinterleaver302. Therefore, without further adaptation, in order to implement the input buffer701using a FIFO based on a second block of random access memory, twice as much memory would be required as is required to implement the deinterleaver701. As one of the main advantages of a convolutional interleaver is that it requires half the amount of memory as the equivalent block interleaver, it would seem that implementing the input buffer701using a FIFO based on a second block of random access memory would remove this advantage of using a convolutional interleaver completely. However, closer examination reveals that the amount of extra memory can be reduced. This is because the pattern of shutdown punctures is deterministic (especially if Nframemod Npors=0), symbols from the next interleaving frame are not required to be shifted because they are not output from the input buffer701to the interleaver during the current interleaving frame, and the complexity in implementing an expanding shift register is caused by the need to be able to shift and expand the input buffer. However, if no shifting is required then implementation is more straightforward. Consequently, an amount of extra memory required to implement the input buffer701using a FIFO can be reduced by dividing the input buffer701input two sections: a first section is used to store symbols from the current interleaving frame, and a second section to store symbols from the next interleaving frame.

FIG. 19illustrates a two section buffer memory arrangement in accordance with an example of the present disclosure, comprising a first section1902for storing symbols from the current interleaving frame and a second section1903for storing symbols from the next interleaving frame. It is unlikely that the symbols in the second section1903will be required to be shifted and therefore a FIFO is only necessary to implement the first section1902as a FIFO. Whilst symbols from the current interleaving frame are passing through the first section1902, it will be required to either expand or shift. Therefore, the maximum number of locations required to implement the first section1902is less than the number of symbols remaining in the interleaving frame after the first shutdown puncture. The maximum size of the first section1902will be reached when the number of shutdown punctures encountered is equal to the number of symbols remaining in the current interleaving frame because at that point the first section will be large enough to store all the remaining symbols in the current interleaving frame.

The maximum size of the first section can be calculated:

Nmax=∑k=1floor⁡(Npors2)⁢k,≅Naddr/4⁢⁢for⁢⁢large⁢⁢Npors
whereNmax—maximum length of the input bufferNpors—number of delay portions in the deinterleaverNaddr—number of memory locations in the deinterleaver

The second section1903may be implemented as a continuous block of memory, which is not required to be shifted and so its implementation using memory locations released from the deinterleaver302is straightforward. As long as the restriction Nframemod Npors=0 is adhered to, memory locations will become free in the order shown inFIG. 17. Therefore, as symbols from the next interleaving frame are encountered they can be stored in memory locations released from the deinterleaver302in the order shown inFIG. 17. Furthermore, as a result of the separate memories and Nframemod Npors=0, the configuration of the stored symbols from the next frame is greatly simplified as explained below.

FIG. 20illustrates the two section memory arrangement described above. The non-shifting memory1903is implemented using the free memory locations2001and the FIFO1902for the symbols of the current interleaving frame uses a separate dedicated buffer memory. If it is considered that a block interleaver uses 100% of a memory then a conventional convolution interleaver use 50%. However, the conventional convolutional interleaver will be unable to separate interleaving frames etc. without adversely affecting latency and capacity. Implementing a conventional interleaver with a buffer formed from vacant memory elements as inFIG. 11allows interleaving frames to be separated and also uses 50% of the memory. However, it also requires complex memory reconfiguration. Utilising the two section memory configuration described above and illustrated inFIG. 20greatly simplifies the operation of the deinterleaver memory when dealing with discontinuity punctures and interleaving frame separation but only requires Nmaxmore symbol memory. Consequently, a convolutional deinterleaver as described above is able to take account of interleaving frame separation and other discontinuities whilst using 62.5% of the memory of a block interleaver and avoiding complex memory management.

Restarting and Reconfiguration

At the time of outputting the last symbol from the current interleaving frame from the deinterleaver, the input buffer1903will contain Naddrsymbols from the next interleaving frame. These need to be input into the deinterleaver in the order shown inFIG. 13.

If the deinterleaver is implemented using, for example, flip-flops, then executing the filling process illustrated inFIG. 13could be done using suitable multiplexing logic. If, however, the deinterleaver is implemented using a random access memory, a first method of executing the filling process illustrated inFIG. 13is to read out the data from the input buffer symbol by symbol and to write this into the deinterleaver memory elements. However, in cases where the input buffer is implemented using memory locations released from the deinterleaver, care must be taken if following this method to ensure that data is not overwritten when executing the filling process illustrated inFIG. 13. Another disadvantage of that method is that reading and writing data symbol by symbol may take more time than is available. A second method of transferring the data from the input buffer to the deinterleaver memory, considering that they are both implemented using the same physical memory, is to execute the transfer instantaneously by changing the memory mapping of the memory. It turns out that this method is straightforward, because the entirety or second section of the input buffer is implemented using memory locations released from the deinterleaver in the order shown inFIG. 17. ComparingFIG. 13andFIG. 17shows that simply reversing the order of column numbering has the desired effect.

FIG. 21illustrates the deinterleaver302when the shutting down and the starting up of the deinterleaver302is due to the reconfiguration of the interleaver204and deinterleaver302. Reconfiguration may be required when the size of the interleaver204and deinterleaver302is to be altered. If the size of an interleaver204and a deinterleaver302is changed then there will necessarily be a change in the latency through them. The techniques described thus far are not likely to be able to be used to account for a change in latency caused by a change in the size of the interleaver204and deinterleaver302, instead some other mechanism such as there being gaps in the transmitted data or there being a data smoothing buffer in the receiver is required.

For example inFIG. 21the size of the deinterleaver302has been increased due to the addition of an extra column of memory elements2101. In order to account for this increase, symbols are first input into the pre-existing memory elements404as set out above and then symbols are input into the remaining vacant memory elements in the order they are received and taking into account any subsequent discontinuities, discontinuity punctures, and symbols affected by discontinuity punctures.

FIG. 22illustrates the deinterleaver302when the size of the deinterleaver302has been reduced. The previously described technique for the input of symbols from the input buffer701can be utilised to fill the available memory elements404of the delay portions403. However, remaining data must either be buffered upstream from the deinterleaver302or could be buffered by using the remaining and now unused memory locations associated with memory elements used as a buffer2201.

Various modifications may be made to embodiments herein before described. For example, other memory management techniques may be used to implement the deinterleaver, the delay portions, memory elements, and the input buffer. The functional elements of the deinterleaver herein before described may also implemented using a variety of means, for instance the controller and memory management elements may be implemented as circuitry, circuits, parts of circuits, logic, processors or parts of processors. Similarly, the blocks of the transmitter and the receiver, the delay portions, memory elements, memory locations and section of the input buffer may be implemented using a variety of means for example, such as through a combination of volatile and non-volatile memory, circuitry, circuits or parts of circuits, logic, or processors or parts of processors. The described deinterleaving techniques may also be implemented in any suitable communications network or communications architecture.

The following numbered clauses provide further example aspects and features of the present technique:

1. A receiver for receiving a signal comprising an interleaved symbol stream, the receiver comprising:convolutional deinterleaver circuitry comprising a plurality of delay portions each of which is arranged to delay symbols from the symbol stream from an input to an output by a different amount, the delay portions being arranged in a sequence;an input selector configured to input the symbols from the symbol stream to the delay portions so that successive symbols are input in accordance with the sequence of the delay portions;an output selector configured to read the symbols from the delay portions by successively selecting the symbols from the outputs of the delay portions in accordance with the sequence of the delay portions to form a deinterleaved symbol stream;andcontroller circuitry configuredto detect a discontinuity puncture in the interleaved symbol stream resulting from symbols being punctured from the interleaved symbol stream; andto identify symbols in the interleaved symbol stream affected by the discontinuity puncture, the identified symbols in the interleaved symbol stream being symbols which would be out of sequence in the deinterleaved symbol stream as a result of the discontinuity puncture,to store the identified symbols, andto input the identified symbols to the delay portions to compensate for the discontinuity, wherein at least one of the delay portions is formed from one or more memories and at least one of the identified symbols is stored in the one or more memories of the delay portions, which would have been occupied by the symbols which had been punctured from the interleaved symbol stream.

2. A receiver according to clause 1, wherein the symbols are input to and read out from the delay portions in a first direction in accordance with the sequence of delay portions and the controller is configured to determine a reference number (Nref) for each symbol in the interleaved symbol stream, the reference number identifying the order in which the symbols should be read out to form the deinterleaved symbol stream, and the reference number is calculated in accordance with
Nref=(Niter−Npors+1)Npors+(Npors+1)Npor
where Nporis a position of a delay portion relative to the other delay portions, Nporsis the total number of delay portions and Niterrepresents a number of iterations through the sequence of delay portions.

3. A receiver according to clause 1, wherein the symbols are input to and read out from the delay portions in a second direction in accordance with the sequence of delay portions and the controller is configured to determine a reference number (Nref) for each symbol in the interleaved symbol stream, the reference number identifying the order in which the symbols should be read out to form the deinterleaved symbol stream, and the reference number is calculated in accordance with
Nref=(Niter−Npor)Npors+Npor
where Nporis a position of a delay portion relative to the other delay portions, Nporsis the total number of delay portions and Niterrepresents the number of iterations through the sequence of delay portions.

4. A receiver according to clauses 2 or 3, wherein the controller is configured to detect a discontinuity puncture in accordance with Nref<0 for the input symbol.

5. A receiver according to clauses 2 or 3, wherein the symbols of the interleaved symbol stream are divided into interleaving frames, the discontinuity punctures resulting from a transition between frames, and the controller is configured to detect a discontinuity puncture in accordance with Nref≥Nframefor the input symbol, where Nframerepresents the number of symbols remaining in a current interleaving frame.

6. A receiver according to clause 5, wherein the symbols stored in the one or more memories of the delay portions which would have been occupied by symbols that have been punctured from the interleaved symbol stream, form the next interleaving frame.

7. A receiver according to clause 5 or 6, wherein the receiver comprises a buffer and one or more of the identified symbols that form part of the current frame are stored in the buffer, the buffer being formed from memories other than the memories of the delay portions.

8. A receiver according to clause 7, wherein
NframemodNpors=0.

9. The receiver according to clause 8, wherein the maximum size (Nmax) of the buffer is given by

10. The receiver according to any preceding claim, wherein the signal comprises synchronisation data indicating the position of the selectors, and the controller is configured detect the synchronisation data and to position the selectors in accordance with the synchronisation data.