Title of Invention	METHOD OF SELECTING A GENERATOR MATRIX FOR ENCODING INFORMATION WORDS
Abstract	A method of selecting a generator matrix, for encoding information w.ords comprising information symbols into codewords of a code provides an enhanced error correction capability if at least one information symbol is known a priori to a decoder decoding received, possibly mutilated codewords. In order to design a code of which the correction power is enhanced if some information symbols are known to the decoder prior to decoding the generator matrix is selected such that the minimum Hamming distance of at least one subcode of the code is larger than the minimum Hamming distance of the code and that a subcode generator matrix of the at least one subcode is derived from the generator matrix of the code by omitting the at least one row from the generator matrix corresponding to the at least one a priori known information symbol.

Title of Invention

METHOD OF SELECTING A GENERATOR MATRIX FOR ENCODING INFORMATION WORDS

Abstract

A method of selecting a generator matrix, for encoding information w.ords comprising information symbols into codewords of a code provides an enhanced error correction capability if at least one information symbol is known a priori to a decoder decoding received, possibly mutilated codewords. In order to design a code of which the correction power is enhanced if some information symbols are known to the decoder prior to decoding the generator matrix is selected such that the minimum Hamming distance of at least one subcode of the code is larger than the minimum Hamming distance of the code and that a subcode generator matrix of the at least one subcode is derived from the generator matrix of the code by omitting the at least one row from the generator matrix corresponding to the at least one a priori known information symbol.

Full Text	CODING AND DECODING OF PARTIALLY A PRIORI KNOWN INFORMATION The invention relates to a method of selecting a generator matrix for encoding information words comprising information symbols into code words of a code for providing an enhanced error correction capability if at least one information symbol is known a priori to a decoder decoding received, possibly mutilated code words. The invention relates further to a method of encoding information words into code words and to a method of decoding possibly mutilated code words of a code into information words. Still further, the invention relates to a corresponding apparatus for encoding information words, to a corresponding apparatus for decoding possibly mutilated code words, to a computer program implementing said methods, to a data carrier for recording user data and to a signal for transmitting user data. The concept of using a generator matrix for encoding information words into code words is widely used and known, e.g. from Richard E. Blalut "Theory and Practice of Error-Control Codes", Addison Wesley, May 1984, Sec. 3.2. Such a generator matrix is particularly used and described in standards, like the CD audio standard. As a particular example for the use of a systematic algebraic code for the protection of information against errors, in the field of address retrieval on optical media the sector address on optical media is part of a header which is protected by an error correcting code. Under many circumstances, c. g. if consecutive sectors are to be written or read, or in case of an enforced track jump to an approximately known disk area, much of the header information of the current sector can be inferred from the previously read sectors and the table of contents. However, for known codes partial knowledge of information symbols hardly leads to an improved error correction capacity of the code. The present invention therefore relates to coding for a channel producing symbol errors, where a side-channel which is not known to the encoder possibly informs the decoder about a part of the information that is encoded in the transmitted codeword. It is an object of the present invention to design a code the error correction power of which is enhanced if some information symbols are known to the decoder prior to decoding. It is a further object of the present invention, to provide a method of encoding information words into codewords and a method of decoding a possibly mutilated codeword encoded by such a method of encoding. Further, corresponding apparatuses shall be provided. These objects are achieved by a method of selecting a generator matrix of claim 1, according to which said generator matrix is selected such that the minimum Hamming distance of at least one subcode of said code is larger than the minimum Hamming distance of said code and that a subcode generator matrix of said subcode derives from said generator matrix of said code by smitding the at least one row from said generator matrix corresponding to said at least one a priori known information symbol. These objects are further achieved by a method of encoding as claimed in claim 7 and a method of decoding as claimed in claim 12. According to the present invention the mapping of information words onto codewords is such that the decoder can enhance the effective Hamming distance if some information symbols of the information words are known. However, it is assumed that the decoder is not informed about which, if any, symbols are actually known to the decoder. To get such an enhancement of the effective Hamming distance a certain predefined (i.e. previously selected) generator matrix is used. Said predefined generator matrix is then used for encoding and decoding, i.e. it needs to be used as a standard generator matrix. In other words, the generator matrix is selected such that the minimum Hamming distance of a subcode is larger than the minimum Hamming distance of the complete code. When using said predefined generator matrix address information can be protected more reliably. If part of the address information, e. g. the most significant bits, is already known to the decoder if a new conomand to access a certain address on a data carrier, e.g. a disk, is given, address retrieval is more reliable which is especially important during writing. The decoder can then effectively use a subcode having an increased minimum Hamming distance. However, if no information symbols are known to the decoder a priori, decoding of the retrieved codeword is possible as usual and the Hamming distance of the code used according to the invention will be the same as the Hamming distance of known codes, i.e. no subcode with a larger minimum Hamming distance can be used during decoding. When receiving a possibly mutilated codeword, e. g. by reading it from a data carrier, and in the case where at least one information symbol is known to the decoder a priori, e. g. the most significant bits of a read address, the decoder first encodes the known information symbols by using the corresponding rows of said generator matrix which has already been used to encode the corresponding information word of said information symbols into a codeword and then adds the result giving an intermediate word. Such intermediate word is thereafter subtracted from the received codeword which is to be decoded. The result is then decoded by a known decoding method using a subcode generator matrix comprising only that part of the generator matrix used for encoding the information word which corresponds to the unknown information symbols, i. e., from the generator matrix used for encoding, the rows corresponding to the information symbols known a priori to the decoder are omitted, and the decoder does only use the remaining rows of the generator matrix as a subcode generator matrix for decoding the result of said subtraction. This means that in the subcode generator matrix only the rows of the generator matrix appear that do not correspond to the a priori known information symbols. When selecting the generator matrix as described above the error correction power can be enhanced if some information symbols are known to the decoder prior to decoding. There may be different levels of improvement depending on which and how many information symbols are known to the decoder. A preferred embodiment of the invention is given in claim 2. According to this embodiment the generator matrix of the code comprises at least two subcode generator matrices all having different number of rows wherein all rows of such subcode generator matrices are part of said generator matrix, i.e. the subcodes deriving from said subcode generator matrices are nested in said code deriving from said generator matrix. Each row of the generator matrix can also be regarded as representing a polynomial each having a certain number of zeros. According to the present embodiment certain zeros are common to each polynomial, i. e. to each polynomial represented by one row of the generator matrix. However, each polynomial differs from each other polynomial in at least one zero. With this embodiment it can be achieved that the Hamming distance increases with the number of information symbols known a priori to the decoder. The generator matrix may also be selected such that its error correction capacity increases with an increasing number of information symbols which are a priori known to the decoder. The generator matrix may further be selected such that the Hamming distance of all proper subcodes of said code generated by some, but not all, rows of the generator matrix is larger than the Hamming distance of said code. This has the advantage that already in the case where one information symbol is known a priori to the decoder the code has an improved error correction capacity no matter which information symbol is known a priori. Further preferred embodiments of the method of selecting said generator matrix are defined in claims 3 to 6. A method of encoding information words into codewords according to the invention is defined in claim 7; preferred embodiments thereof are given in claims 8 to 11. A method of decoding possibly mutilated codewords into information words according to the invention is defined in claim 12; preferred embodiments thereof are given in claims 13 to 18. The method for decoding a possibly mutilated codeword according to the invention is generally characterized in that said information words are encoded into said codewords using a generator matrix selected according to the invention and that the contribution of said at least one a priori known information symbol included in said possibly mutilated codeword is taken into account for decoding said possibly mutilated codeword with enhanced error correcting capabilities. In a preferred embodiment the contribution of said at least one a priori known information symbol included in said possibly mutilated codeword is subtracted from said possibly mutilated codeword before decoding said possibly mutilated codeword. A preferred embodiment of the invention is based on code puncturing. Therein a larger intermediate generator matrix is used to encode the information words into intermediate codewords having a greater length than codewords encoded using the normal generator matrix. From these intermediate codewords, however, some symbols are omitted to obtain the final codewords. During decoding a received possibly mutilated codeword is first extended by use of the a priori known information symbols to obtain a pseudo codeword which is then decoded using said intermediate generator matrix used during encoding. The obtained second pseudo codeword is thereafter input into an error and erasure decoder, preferably of a known construction, retrieving the information word. One main advantage of this embodiment is that a larger minimum Hamming distance can be achieved irrespective if the information symbols known a priori are known in a successive order or not. Even if the information symbols are not known successively the minimum Hamming distance of a subcode can be increased by each additional known information symbol if the generator matrix is selected and used according to this embodiment of the invention. An advantageous application of the present invention lies in the field of address retrieval, in particular on optical media. When using the invention an address or timing information can be protected by a higher error correction capacity making an address retrieval more secure and accurate. The invention can further be used for securing address information in a serial data stream, which is for example transmitted over a transmission line like a telecommunication system or the internet. In general, the invention can be used for protecting information by a code having an improved - compared to known codes - error correction capacity if part of the information is known a priori to the decoder. An apparatus for encoding information words and an apparatus for decoding a possibly mutilated codeword according to the invention are defined in claims 23 and 24. It shall be understood that these apparatuses can be developed further and can have similar embodiments which have been explained above with reference to the method of selecting a generator matrix according to claim 1. A computer program according to the invention for implementing any or all methods according to the invention is defined in claim 25, A data canier according to the invention is defined in claims 26 and 27. Such a data carrier is preferably used for storing audio, video or software data and might of a recordable or rewriteable type, in particular an optical record carrier like a CD or a DVD. A particular application lies in the field of digital video recording (DVR). Generally, such a data carrier comprises system data items, in particular system data items of address data, timing data or position data, which are already recorded on the data canier at the production site of the data carrier and which are akeady present an empty data carrier for recording user data is bought. The invention may thus be used for encoding said system data items. However, the invention may as well be used for encoding user data. Still further, a signal for transmitting user data, said signal including system data items, e.g. position, address or timing data, encoded by a method according to the inventions is defined in claim 28. The invention will now be further explained in more detail with reference to the drawings, in which: Fig. 1 shows the conventional format of a codeword. Fig. 2 shows a block diagram of the encoding and decoding scheme, Fig. 3 shows an apparatus for encoding information words according to the invention, Fig. 4 shows an apparatus for decoding according to the invention, Fig. 5 shows another embodiment of an apparatus for encoding according to the invention, Fig. 6 shows still another embodiment of an apparatus for encoding according to the invention, Fig. 7 shows an embodiment of an apparatus for decoding according to the invention, Fig. 8 shows means for extracting information symbols from a codeword used in the apparatus for decoding shown in Fig. 7, Fig. 9 shows still another embodiment of an apparatus for encoding according to the invention, and Fig. 10 shows a corresponding apparatus for decoding according to the invention. Fig. 1 shows the typical scheme of codewords c of a [n, k] block code, e.g. a Reed-Solomon-Code. A codeword comprises an information word m comprising k information symbols and a parity word p comprising n-k parity symbols generated when encoding said information word m into a codeword c. Fig. 2 shows a block diagram of a typical system using encoding and decoding. Therein user data, e.g. audio or video data, coming from a data source 1, e.g. recorded on a master tape or master disk, are encoded before they are stored on a data carrier, e.g. a disk, or transmitted over a transmission channel, e.g. over the internet, before they are again decoded for forwarding them to a data sink 9, e.g. for replaying them. As can be seen the user data of the source 1 are first encoded by a source encoder 2, then error correction encoded by an ECC encoder 3 and thereafter modulated by a modulator 4, e.g. an EFM modulator, before the encoded user data - the codewords - are put on the channel 5 on which errors may be introduced into the codewords. The channel 5 shall here interpreted broadly, including a transmission channel as well as storage of the encoded data on a data carrier for a later replay. When replay of data is intended the encoded data first have to be demodulated by a demodulator 6, e.g. an EFM demodulator, before they are error correction decoded by an ECC decoder 7 and source decoded by a source decoder 8. Finally the decoded user data can be input to the sink 9, e.g. a player device for replay of the user data. Such a general system is, however, not only used for encoding and decoding user data, but may as well be used for any kind of data like management data, in particular address data. Such address data are used to find a certain location on a data carrier or in a data stream of user data. On recordable or rewriteable disks such address data are generally prerecorded on the empty disks before any user data are recorded. The present invention refers to encoding and decoding of data. Therein a certain predetermined generator matrix is used the selection of which is also referred to by a method according to the invention. A particular application of the invention lies in the field of address retrieval of addresses used on optical record carriers. Fig. 3 shows an embodiment of an apparatus for encoding information words m according to the present mvention. Therein the encoding apparatus 10 comprises an encoding unit 11 for encoding the information words m comprising a fixed number of information symbols m1, m2,..., mk into codewords c of a code C. To achieve an improved error correction capacity a certain predefined generator matrix G is used for encoding the information words m. This generator matrix G is selected and defined once by a selection unit 12 and then provided or preferably stored in the encoding apparatus 10 and the decoding apparatus for continuous use. By use of the generator matrix G the information words m are thus encoded into codewords c by the encoding unit 11. These codewords c can be provided to a writing unit 13 recording the codewords c on an optical record carrier 14, e. g. on a CD or a DVD. By way of an example the invention, in particular a preferred selection of the generator matrix G, shall be explained in more detail. The example is based on the [7,4, 3] binary Hamming code C generated by g(x) = x3 + x + 1. At first the "normal" known use of the code shall be explained while thereafter the use of a code according to the invention shall be explained. having four (in general k) rows and seven (in general n) columns. An information word m = (m1, m2, m3, m4) is mapped onto the codeword c = m • Gsys. If the i-th information symbol mi is known to the decoder prior to decoding, the decoder can subtract the contribution of m1 to the received word r prior to decoding. This means that the decoder decodes the residual received word r - mj • Gsys1 where Gsys1 indicates the i-th row of Gsys, to a code where the i-th row is removed from the generator matrix Gsys- The knowledge of up to any three information bits does not alter significantly the correction capacity for the unknown information bits, since almost all subcodes C' of the code C obtained by deleting at most three rows of Gsys still have Hamming distance three. Only if the information bits m1, m3 and m4 are known, the Hamming distance for retrieving m2 is increased to four. According to the present invention, another generator matrix G,d for the same If the (non-systematic) generator matrix G1d is used for the encoding of the code C, an informed decoder as shown in Fig. 4 can decode to more favourable subcodes C of the code C if certain infonnation bits or information symbols - an information symbol may comprise more than one bit - are known. For example, if the decoder knows the first information bit mi it can use the subcode C generated by the last three rows ga, g3, g4 of Gid, which corresponds to a [7, 3,4] simplex code. As another example, if the last three bits m2, m3, m4 are known to the decoder, it can exploit the subcode generated by the first row of G1d which corresponds to the [7,1,7] repetition code, thus enabling the decoder to recover m1 reliably even in the presence of three bit errors. An apparatus for decoding a read possibly mutilated codeword r is shown in Fig. 4. Therein the decoding apparatus 20 receives the possibly mutilated codeword r which has been read from the data carrier 14 by a reading unit 21. Assuming that an infonnation word m encoded in a codeword c comprises four information symbols m1, m2, m3, m4 and assuming further that the apparatus 20 for decoding a priori knows three information symbols m2, m3, nu, in a first step said known information symbols m2, m3, nu are encoded by anencoding unit 22 using the generator matrix G which is stored in the encoding apparatus 20 in a storage unit 23 and which had already been used for encoding the codewords c which are stored on the data carrier 14 and read as possibly mutilated codewords r. For such encoding the encoding unit 22 uses the rows of the generator matrix G which correspond to the known information symbols m2, m3, m4. In a subsequent step the result of such encoding, i.e. the products of the known information symbols m2, m3, m4 with their corresponding rows g2, g3, g4 of the generator matrix G1d, are added by a summing unit 24 giving an intermediate word s. In a subtracting unit 25 the intermediate word s is subtracted from the read codeword r, and the result of such subtraction is provided to a decoding unit 26. Therein the subcode C which is generated by using a subcode generator matrix G' is decoded wherein the subcode generator matrix G' derives from the generator matrix G in the forming means 27 by omitting all rows from the generator matrix G which correspond to the known information symbols m2, m3, m4, i.e. in the present example by omitting the rows ga, ga, g4. So in the present example, the subcode generator matrix G' does only comprise the first row g1 of the generator matrix G. As a result the unknown information symbol m1 can be retrieved such that the complete information word m is finally known. In general, thus the contribution of said a priori known information symbols included in the possibly mutilated codeword is subtracted from said possibly mutilated codeword, and the result of said subtraction is decoded. The method of decoding shall now be explained in more detail by way of an example. The codewords c of a code C shall be given by In general the generator matrix G comprises k rows and n columns, the information word m comprises k columns and a codeword c comprises n columns. Assuming now that the information symbols ma, ms, nu are known a priori to a decoder and that a read codeword r is given by the sum of the stored codeword c plus an additional noise n the intermediate word s is first computed as Thereafter a difference between the read possibly mutilated codeword r and the intermediate word s is calculated as: Therein the information symbol m1 can only be 0 or 1 if the information symbol mi comprises one bit, the row g1 of the generator matrix G is fixed and the noise n is unknown. Using now the above given generator matrix Qd selected according to the invention gi is given as (1 11 1 11 l)such that m1 g1 can only be (0000000) or (1 11111 1). If the before mentioned calculation of m1 g1 + n has for example resulted in (0 0 1 0 0 1 1) the probability will be higher that m1 g1 is given as (0 0 0 0 0 0 0) leading to the result that m1 has bit value 0. As can be seen from this example the information symbol m1 can be detennined despite three bit errors in the read codeword which means that the remaining subcode C has Hamming distance seven. . The invention can also be illustrated by way of a simple example which may be used for a fast reliable address retrieval. Conventionally, a [7,4,3] binary Hamming code is generated by the generator polynomial g(x) = x3 + x + 1. Each codeword is a binary polynomial multiple of the generator polynomial g(x). If a systematic encoder is used the information bits appear un-altered in the high order positions, while the parity bits are in the low order positions. Below, a list of all 16 codewords of the code is given wherein the coefficients of each codeword polynomial are given as a vector. The highest order symbol c6 is at the left, while the lowest order symbol CQ is at the right hand side of each codeword. The four left most bits c6.. .c3 correspond to the four information bits mj.. .mi, and the three right most bits C2, C1, C0 are the parity bits p3, p2, p1. By inspection, it can be checked that any two codewords differ in at least three positions, which means that the Hamming distance of the code equals three so that one error can be corrected: As an example, the fifth codeword from the top equals 1 • g(x) (in polynomial notation), the fourth codeword from the top equals x • g(x) and the tenth codeword from the top equals x2 • g(x). Important to know is that the (mod 2) sum of any two codewords is again a codeword, because this is a linear code over GF(2), i. e., the code forms a group. Each information bit is protected against one bit error, and any knowledge about some information bits does not increase the correction capacity of the other information bits. According to the present invention the mapping of information bits into codewords is changed such that knowledge about at least one, in the given example of three, information bit increases the correction capacity for the remaining, in the example the forth, information bits. In the following the three left most information bits nu, ms, m? may be called the MSB (Most Significant Bits) of an address, and the last information bit mi may be called the LSB (Least Significant Bit) of an address. The code construction according to the present invention is such that, if MSB is known, a strong code for extracting LSB is achieved. If none of the information bits is known a priori the error correction capacity is not changed compared to the error correction capacity of the conventional code. According to the invention use is made of the linearity of the code. For the encoding of MSB simply those systematic codewords in the above table are used that have m1 = 0. It is to be noted that there are indeed 8 of those codewords. If c (MSB) is the result of this encoding, in order to also encode LSB, c (LSB = 0) = 0000000 and c (LSB = 1) = 1111111 is chosen. The final codeword c that is transmitted equals c = c (MSB) + c (LSB), where the "+" indicates a vector addition over GF(2). It is to be noted that c again belongs to the code (die table) because of the linearity of the code (over GF(2)). It is further to be noted that the effect of adding c (LSB) to c (MSB) scrambles the value of MSB, i. e. if LSB = 1, the values of MSB are inverted. So the overall code is not systematic anymore in all its information bits. If such a codeword c is transmitted via some channel bit errors may be introduced in the codeword. A received codeword may thus be mutilated and will be called possibly mutilated codeword r which deviates from the codeword c in the error positions. If nothing is known about the information bits, it is only known that the transmitted codeword c belongs to the Hamming code, so that always one bit error can be corrected. After error correction which supposedly restores the codeword c from the received word r the information can be retrieved by first extracting LSB (the information symbol m1) which equals the fourth bit in the codeword c, and with the given LSB either (0 0 0 0 0 0 0) or (1 1 1 1 1 1 1) is subtracted from the codeword c dependent on LSB = 0 or LSB = 1, respectively. Thereafter, MSB is available as the first three bits of the result. If there is more than one transmission error, there will, however, be made errors in the decoding result which always happens with a single error correction Hamming code. Suppose, however, that MSB is known before decoding, First, the most significant part c(MSB) of the codeword is reconstructed by the decoder and thereafter subtracted from the received word r. Then either (0 0 0 0 0 0 0) or (1 1 1 1 1 1 1) is left, still corrupted by the channel errors. Because the distance of these two words equals 7, LSB can be found even in the presence of 3 bit errors. Thus, by using only three parity bits for the overall code, LSB is effectively protected by a [7,1, 7] repetition code if MSB is known. In this example the [7,4,3] Hamming code is divided into a [7,1,7] subcode and co-sets of this code. As already explained the invention may be used for protecting addresses which are used on optical record carriers. However, the invention may also be used for protecting addresses in any serial data stream which may also be transmitted over a transmission line. In general, the invention may be applied in any application where information words shall be encoded into a code and where an improved error correction capacity shall be achieved if at least one information symbol is known a priori to the decoder. In more general terms the invention may be applied to any linear code, in ' particular Reed Solomon codes. A [n, k, n-k+1] RS code can be subdivided into multiple subcodes such that if the j most significant information symbols are known, the effective distance for decoding the remaining k-j information symbols equals n-k+l+j. The decoding procedure also consists of re-encoding the j known information symbols, subtracting the result of this re-encoding from the received word and use the appropriate decoder for I decoding the high distance subcode that is left. In another embodiment of the present invention the generator matrix G can be selected such that at least two subcodes are nested in the code generated by said generator matrix G. This shall be illustrated by way of the following example. According to the invention the generator matrix G shall be selected as G = (g1(x) g2(x) gaCx))T wherein I where a is an element in GF(8) satisfying a3 = 1 + a. The corresponding generator matrix thus results in The codewords c(x) of the code C are therefore polynomial multiples of the generator polynomial g3Cx). The code C generated by this generator matrix G thus has minimum Hamming distance three as will be clear from the above mentioned reference of R. Blahut at section 7.2. Assuming that the information symbol ma of an information word m = (nii ma m-i) is known a priori to the decoder the subcode Ca" generated by the corresponding subcode generator matrix 02" = (gi g2)^ and having minimum Hamming distance four can be employed. In such subcode C2' all codewords are combinations of the generator polynomials g1 and g2. If the information symbols mz and m3 are known the subcode C1 generated by the subcode generator matrix G1 = (gi) and having minimum Hamming distance five can be employed. In addition with the above selection of the generator matrix G less muItiplications are required for the calculation of the codewords c = m G since some of the generator polynomials are polynomial multiples of other generator polynomials. As can be seen from the above example the subcodes C1 and C2' are nested in the code C and each subcode C1 C2' is generated by a corresponding subcode generator matrix G1 G2'. Each of said subcode generator matrices G1, G2' has a different number of rows wherein all rows are part of said generator matrix G. In general the selection of G can be such that each subcode generator matrix includes an increasing number of rows and each subcode generator matrix can be achieved from the another subcode generator matrix by omitting one row. In the above example the subcode generator matrix G1 derives from the subcode generator matrix G2' by omitting the second row, i. e. by deleting the generator polynomial g2(x). The subcode generator matrix G2' derives from the generator matrix G by deleting the last row of G, i, e. by deleting the generator polynomiar g3(x). The generator matrix G can also be selected such that the first i rows, i being an integer number equal to or larger than l,.fonn a subcode generator matrix G1 for obtaining a subcode Ci' wherein the Hamming distance is larger than for a subcode Q1 obtained from a subcode generator matrix G1+1which is formed by the first i+1 rows of said generator matrix G. In more general terms the code C can be an RS code over GF(q) with generator polynomial . wherein a is a primitive element in GF(q). The codewords of the code C are represented by polynomials c(x) of degree at most n-1 which are polynomial multiples of the generator polynomial gk(x). According to the invention it is proposed to encode the information symbols mo, mi,..., mt.i into The information word m is thus encoded with a generator matrix G for which the j-th row consists of the coefficients of the polynomial gj(x). The w top rows of the generator matrix G represent the polynomials gi(x), g2(x), ..., gw(x), all of which are multiples of gw(x). Consequently, these top w rows generate an [n, w, n-w+1] residual code. Hence, if the decoder is informed about (mw, ..., mk-i), then it can correct up to 0.5 (n-w) errors, using a decoder for the RS code with generator polynomial gw(x). It is to be noted that the residual codes for consecutive w's are nested subcodes of the original RS code C, Another efficient encoding method consists of the following steps. At first the first codword parameter c'(x) is initialized by c\x) = mi. Thereafter for j=2 to k the subsequent codeword parameters c(x) are computed by Finally, the codeword polynomial c(x) is computed by The coefficients of said codeword polynomial c(x) together form the codeword Another preferred embodiment of the invention shall now be explained with reference to Figs. 5 to 8. In Figs. 5 and 6 two embodiments of an encoding apparatus according to the invention for frequency domain encoding, in Fig. 7 a corresponding decoding apparatus is shown, and in Fig. 8 an extracting unit which is part of the decoding apparatus of Fig. 7 is shown in more detail. Frequency domain encoding and decoding shall be explained by way of the detailed example in the field of digital video recording (DVR). In the example an address information comprising 5 address symbols and 1 auxiliary symbol, together forming 6 information symbols, shall be encoded into a wobble code stored in a wobble signal. In the particular example a [11, 6,6] Reed-Solomon-like code over a Galois field GF (16) shall be used wherein a as a primitive element. The codewords c are thus of the form c(x) = C0 + c1x The 6 information symbols (also called user symbols) shall be labeled as m5, m6..., m10 i- e. symbols mo to m4 are not used in this particular example. A generator polynomial g(x) is given as If no information symbol is known to the decoder said code has a minimum Hamming distance of six. However, if information symbol ms is known the minimum Hamming distance is increased by one. With each additional successive information symbol known to the decoder also the minimum Hamming distance is increased by one. Before implementing the encoding rule several definitions have to be made which will be explained in the following. A parent generator polynomial g(p)(x) is defined by The coefficients of said codeword polynomial c(x) then form the codeword c in the code C. The implementation of this encoding rule using a feed forward register is shown in Fig. 5. As can be seen therein in a first portion the information symbols m5 to m10 are at first multiplied with certain parameters, fed to respective feedback shift registers and then summed up. Thereafter the sum is inputted to the feed forward shift register including the coefficients of the parent generator polynomial to form the codeword polynomial c(x). The general definitions for implementing a frequency domain encoding of an information word m comprising k information symbols mn-k. nin-k+i,..., nin-i into a codeword of an [n,k,n-k+l] Reed-Solomon code over GF(q) are as follows: The parent generator polynomial (g(p)(x)) is given as The difference between the encoding rules of Figs. 5 and 6 is that in the encoding rule of Fig. 6 the information symbol mn is directly used and that the encoding method implemented in the apparatus of Fig. 6 is a hybrid method of frequency and time domain encoding while the encoding method implemented in the apparatus of Fig. 5 is a method for pure frequency domain encoding. The general definitions for implementing the hybrid encoding of an information word m comprising k information symbols ma-k, nin-k+i,..., ma-1 to a codeword of an [n,k,n-k+l] Reed-Solomon code over GF(q) are as follows: The parent generator polynomial (g(t)(x)) is given as in common. Therefore the following properties of the parent and the component generator polynomials can be used for the extraction of the information symbols: A corresponding decoding apparatus is shown in Fig. 7. Therein it is assumed that a received word r(x) comprising symbols ro, ri,..., tn is a possibly mutilated codeword, i. e. includes a codeword c plus noise n. From the received word r syndromes Sj are computed according to a known method in a syndrome forming unit 30 wherein it holds that A detailed embodiment of said extracting unit 33 is shown in Fig. 8. As shown before, the Hamming distance of the described code increases to kmax + 2 if information symbols ms, mg,.,., mkmax are known thus enabling a more reliable address recognition. The increase in Hamming distance does not cost an extra redundancy and the decoder of the code might be a usual decoder which is capable of computing some extra syndromes. Knowledge of some information symbols thus allows to update and subsequently use the syndromes corresponding to these information symbols. In more general terms the syndromes Sj are computed by Yet another embodiment of the invention based on code puncturing shall now be expl^'ned with reference to Figs. 9 and 10. Fig. 9 illustrates the method of encoding an information word m into a codeword c and Fig. 10 illustrates the method of decoding a possibly mutilated codeword r into an information word m. As shown in Fig. 9 the information word m comprising k information symbols is encoded by an encoding unit 41 of an encoding apparatus 40 using an intermediate generator matrix C. Said intermediate generator matrix G"derives from a generator matrix G which has been selected by a selection unit 42. The intermediate generator matrix G' is larger than the generator matrix G in that it comprises at least one more column than the generator matrix G. In general, the generator matrix G has k rows and n columns while the intermediate generator matrix G" has k rows and n+k columns and comprises k columns with a single non-zero entry at mutually different positions. When using said intermediate -generator matrix G' for encoding the information word m, intermediate codewords t having k + n symbols are obtained. From said intermediate codeword t the codeword c is obtained from a codeword generating unit 44 by omitting a number of symbols of said intermediate codeword t. Therein the number of symbols to omit corresponds to the difference between the number of columns of said intermediate generator matrix G' and said generator matrix G. Thus, the obtained codeword c comprises n symbols. During decoding a possibly multilated codeword r comprising n symbols is received by a decoder as shown in Fig. 10. In a first step the received word r is extended into a first pseudo codeword r' by an extension unit 50. Therein said intermediate generator matrix G'" which has already been used in the encoder is used to determine the length of said pseudo codeword r', i. e, the number of symbols of said pseudo codeword r' corresponds to the number of columns of said intermediate generator matrix C, i. e. to the n symbols of the received word r k erasures are added to obtain the pseudo codeword r'. Thereafter, in a replacement unit 51a priori known information symbols, e.g. m1, m5, m6, are replaced in said pseudo codeword r" at positions of the erasures which correspond to the positions of said a priori known information symbols. This means that the erasures 1, 5 and 6 are replaced by the a priori known information symbols m1, m5, m6. The obtained second pseudo codeword r' is thereafter inputted to a decoder unit 52 which is preferably a known error and erasure decoder decoding said second pseudo codeword r' by use of said intermediate generator matrix G" into the information word m comprising k symbols. According to this embodiment of the invention a larger intermediate generator matrix G" is used compared to other embodiments of the invention. However, the advantage of this embodiment is that the information symbols do not need to be known a priori in successive order but any additional information symbol known a priori irrespective of the position of the information symbol within the information word generally leads to an enhanced minimum Hamming distance compared to the code used if no information symbols The rightmost 5 columns of the intemiediate generator matrix C are used as a generator matrix G, i. e, the generator matrix G is The code generated by the generator matrix G has minimum Hamming distance 3. Knowledge of any j information symbols effectively increases the minimum Hamming distance from 3 to 3 + j. CLAIMS: 1. Method of selecting a generator matrix (G) for encoding information words (m) comprising information symbols (m1, m2,..., mk) into codewords (c) of a code (C) for providing an enhanced error correction capability if at least one information symbol (m1, m2, m3) is known a priori to a decoder decoding received, possibly mutilated codewords (r), characterized in that said generator matrix (G) is selected such that the minimum Hanuning distance of at least one subcode (C) of said code (C) is larger than the minimum Hamming distance of said code (C) and that a subcode generator matrix (G') of said subcode (C') derives from said generator matrix (G) of said code (C) by omitting the at least one row from said generator matrix (G) corresponding to said at least one a priori known information symbol (m1 m2, m3). 2. Method according to claim I, characterized in that said generator matrix (G) is selected such that there are at least two subcodes (C1' C2', C3') of respectively increasing Hamming distance, that said subcodes (C1' C2', C3') are nested in said code (C) and that each subcode (C1' C2', C3') is generated by a corresponding subcode generator matrix (G1 G2', G3'), wherein each subcode generator matrix (Gi', G2', G3') has a different number of rows and all rows are part of said generator matrix (G). 3. Method according to claim 2, characterized in that said subcode generator matrices (Gi', G2', G3') include an increasing number of rows, wherein the number increases by one for each generator matrix (G1', G2', G3') and wherein the (i-l)-th subcode generator matrix (Gi') derives from the i-th subcode generator matrix (G2O by omitting one row. 4. Method according to claim 3, characterized in that said generator matrix (G) is selected such that for all integer numbers i, i being an integer number equal to or larger than 1 but at most k-1 where k is the number of rows of said generator matrix (G), a number of i rows forms a subcode generator matrix (G1') for obtaining a subcode (C1) having a larger Hamming distance than a subcode (C1+1) obtained from a subcode generator matrix (G1+1) I formed by a number of i+1 rows of said generator matrix (G). 5. Method according to claim 1, characterized in that said generator matrix (G) derives from a larger, intermediate generator matrix (G"), which has at least one column more than said generator matrix (G) and which generates a code having an increased minimum Hamming distance, by omitting said at least one column having a single non-zero entry. 6. Method according to claim 5, characterized in that said generator matrix (G) has k rows and n columns, that said intermediate generator matrix (G"), having k rows and n+k columns, comprises k columns each with a single non-zero entry at mutually different positions and that said generator matrix (G) derives from said intermediate generator matrix (G") by omitting said k columns. 7. Method of encoding information words (m) comprising information symbols (mu m2, ...,mk) into codewords (c) of a code (C) for providing an enhanced error correction capability if at least one information symbol (mu mi, ma) is known a priori to a decoder decoding received, possibly mutilated codewords (r), characterized in that a generator matrix (G) selected according to a method of claim 1 is used for encoding said information words (m) into said codewords (c). 9. Method according to claim 7, wherein an information word (m) comprising k information symbols (mn-k, mn-k+i, -., mn-i) is encoded to a codeword (c) of an [n,k,n-k+l] Reed-Solomon code over GF(q), said encoding comprising the steps of: a) defining a parent generator polynomial (g^^^(x)) wherein a is a non-zero element of GF(q) of order at most n, and b is an integer number; ci c) computing thie codeword polynomial (c(x)) wherein the coefficients of said codeword polynomial (c(x)) form the codeword (c) in the code (C). 10, Method according to claim 7, wherein an information word (m) comprising k infonnation symbols (mu-k.nia-ic+b ..., mn-i) is encoded to a codeword (c) of an [n,k,n-k+l] Reed-Solomon code over GF(q), said encoding comprising the steps of: defining a parent generator polynomial (g(i)(x)) wherein a is a non-zero element of GF(q) of order at most n, and b is an integer number; b) defining component generator polynomials (g^^^) for n-k c) computing the codeword polynomial (c(x)) wherein the coefficients of said codeword polynomial (c(x)) form the codeword (c) in the code (C). 11. Method according to claim 7, wherein a generator matrix (G) selected according to a method of claim 5 and derived from an intermediate generator matrix (G") is used for encoding said information words (m) into said codewords (c), comprising the steps of: a) generating intermediate codewords (t) by encoding said information words (m) using said intermediate generator matrix (G"), b) generating said codewords (c) from said intermediate codewords (t) by omitting at least one symbol, wherein the number of symbols to omit corresponds to the difference between the number of columns of said intermediate generator matrix (G") and said generator matrix (G). 12. Method of decoding possibly mutilated codewords (r) of a code (C) into infonnation words (m) comprising information symbols (m1, m2, ...,nik), said information words (m) being encoded into codewords (c) of said code (C) using a generator matrix (G) and said code (C) being provided with an enhanced error correction capability if at least one information symbol (m1, m2, m3) is known a priori before decoding, characterized in that said information words (m) are encoded into said codewords (c) using a generator matrix (G) selected according to a method of claim 1 and that the contribution of said at least one a priori known information symbol (m1, m2, m3) included in said possibly mutilated codeword (r) is taken into account for decoding said possibly mutilated codeword (r) with enhanced error correcting capabilities. 13. Method according to claim 12, comprising the steps of: a) encoding said a priori known information symbols (m1, m2, m3) using the corresponding rows of said generator matrix (G) of said code (C), b) adding the results of the encoding step representing an intermediate word (s). c) subtracting said intermediate word (s) from said possibly mutilated codeword (r) to be decoded, d) decoding the result of said subtraction by a known method for decoding the code generated by the rows of the generator matrix (G) that do not correspond to said a priori known information symbols, and e) recovering the information word (m). 14. Method according to claim 12, comprising the steps of: a) forming syndromes (S) from, a received, possibly mutilated codeword (r), b) fonning additional syndromes (S') using said a priori known information symbols (m5, m6,..., mmax) and said possibly mutilated codeword (r), c) calculating the information word (m) using said syndromes (S) and additional syndromes (S'). 15. Method according to claim 14, wherein the information word (m) is calculated by the steps of cl) calculating error locations and error values using said syndromes (S) and additional syndromes (S') to obtain the codeword (c), and c2) extracting the information word (m) from said obtained codeword (c). wherein ma-k,ma-k+i,...,niQ.k+s.i are the known a priori infonnation symbols and wherein said information words (m) are extracted from said obtained codewords by mj = 0(0^""') for n-k ^ j 18. Method according to claim 12, wherein a generator matrix (G) selected according to a method of claim 5 and derived from an intermediate generator matrix (G') is used for encoding said information words (m) into said codewords (c) according to a method of claim 11, comprising the steps of: a) extending said possibly mutilated codeword (r) to a pseudo codeword (r') by adding erasures at positions corresponding to said columns that have been omitted in said intermediate generator matrix (G") to obtain said generator matrix (G), b) replacing the erasures at positions corresponding to said a priori known information symbols (m1, m2, m3) by said a priori known information symbols to obtain a second pseudo codeword (r"), and c) decoding said second pseudo codeword (r') by a known method for error and erasure decoding of a code generated by said intermediate generator matrix (G")- 19. Method according to any one of claims 1, 7 and 12, characterized in that said infonnation words (m) comprise data items wherein successive information words have predetermined corresponding data item elements such that knowledge of a first information word comprising a first data item leads to knowledge of data item elements of one or more successive data items included in subsequent information words, 20. Method according to claim 19, characterized in that said information words (m) comprise address information, in particular address information of positions in a serial data stream and/or of positions on a data carrier. 21. Method according to claim 20, characterized in that said method is applied in digital video recording for encoding an address information into a wobble code to be stored on a data carrier in a wobble signal. 22. Method according to claim 20, characterized in that said information words (m) of said address information comprise multi-bit information symbols. 23. Apparatus for encoding infonnation words (m) comprising information symbols (mi, ma, ...,mk) into codewords (c) of a code (C) for providing an enhanced error correction capability if at least one information symbol (m1, m2, m3) is known a priori to a decoder decoding received, possibly mutilated codewords (r), comprising means for encoding said information words (m) into said codewords (c) using a generator matrix (G) selected by a method according to claim 1. 24. Apparatus for decoding possibly mutilated codewords (r) of a code (C) into information words (m) comprising information symbols (m1, m2, m3) , said information words (m) being encoded into codewords (c) of said code (C) using a generator matrix (G) selected by a method according to claim 1 and said code (C) being provided with an enhanced error correction capability if at least one information symbol(m1, m2, m3) is known a priori before decoding, comprising means for taking the contribution of said at least one a priori known information symbol (m1, m2, m3) included in said possibly mutilated codeword (r) into account for decoding said possibly mutilated codeword (r) with enhanced error correcting capabilities. 25. Computer program for implementing a method of claim 1,7 and / or 12. 26. Data carrier for recording user data, said data carrier having stored system data items encoded by a method according to claim 7. 27. Data carrier according to claim 26, wherein said system data items comprise address data and / or timing data used for finding a position on said data carrier. 28. Signal for transmitting user data, said signal including system data items encoded by a method according to claim 7. 29. Method of selecting a generator matrix for encoding information words substantially as herein described with reference to the accompanying drawings. 30. An apparatus substantially as herein described with reference to the accompanying drawings.

Full Text

CODING AND DECODING OF PARTIALLY A PRIORI KNOWN INFORMATION
The invention relates to a method of selecting a generator matrix for encoding information words comprising information symbols into code words of a code for providing an enhanced error correction capability if at least one information symbol is known a priori to a decoder decoding received, possibly mutilated code words. The invention relates further to a method of encoding information words into code words and to a method of decoding possibly mutilated code words of a code into information words. Still further, the invention relates to a corresponding apparatus for encoding information words, to a corresponding apparatus for decoding possibly mutilated code words, to a computer program implementing said methods, to a data carrier for recording user data and to a signal for transmitting user data.
The concept of using a generator matrix for encoding information words into code words is widely used and known, e.g. from Richard E. Blalut "Theory and Practice of Error-Control Codes", Addison Wesley, May 1984, Sec. 3.2. Such a generator matrix is particularly used and described in standards, like the CD audio standard.
As a particular example for the use of a systematic algebraic code for the protection of information against errors, in the field of address retrieval on optical media the sector address on optical media is part of a header which is protected by an error correcting code. Under many circumstances, c. g. if consecutive sectors are to be written or read, or in case of an enforced track jump to an approximately known disk area, much of the header information of the current sector can be inferred from the previously read sectors and the table of contents. However, for known codes partial knowledge of information symbols hardly leads to an improved error correction capacity of the code.
The present invention therefore relates to coding for a channel producing symbol errors, where a side-channel which is not known to the encoder possibly informs the decoder about a part of the information that is encoded in the transmitted codeword. It is an object of the present invention to design a code the error correction power of which is enhanced if some information symbols are known to the decoder prior to decoding. It is a further object of the present invention, to provide a method of encoding information words into codewords and a method of decoding a possibly mutilated codeword encoded by such a method of encoding. Further, corresponding apparatuses shall be provided.

These objects are achieved by a method of selecting a generator matrix of claim 1, according to which said generator matrix is selected such that the minimum Hamming distance of at least one subcode of said code is larger than the minimum Hamming distance of said code and that a subcode generator matrix of said subcode derives from said generator matrix of said code by smitding the at least one row from said generator matrix corresponding to said at least one a priori known information symbol. These objects are further achieved by a method of encoding as claimed in claim 7 and a method of decoding as claimed in claim 12.
According to the present invention the mapping of information words onto codewords is such that the decoder can enhance the effective Hamming distance if some information symbols of the information words are known. However, it is assumed that the decoder is not informed about which, if any, symbols are actually known to the decoder. To get such an enhancement of the effective Hamming distance a certain predefined (i.e. previously selected) generator matrix is used. Said predefined generator matrix is then used for encoding and decoding, i.e. it needs to be used as a standard generator matrix. In other words, the generator matrix is selected such that the minimum Hamming distance of a subcode is larger than the minimum Hamming distance of the complete code.
When using said predefined generator matrix address information can be protected more reliably. If part of the address information, e. g. the most significant bits, is already known to the decoder if a new conomand to access a certain address on a data carrier, e.g. a disk, is given, address retrieval is more reliable which is especially important during writing. The decoder can then effectively use a subcode having an increased minimum Hamming distance. However, if no information symbols are known to the decoder a priori, decoding of the retrieved codeword is possible as usual and the Hamming distance of the code used according to the invention will be the same as the Hamming distance of known codes, i.e. no subcode with a larger minimum Hamming distance can be used during decoding.
When receiving a possibly mutilated codeword, e. g. by reading it from a data carrier, and in the case where at least one information symbol is known to the decoder a priori, e. g. the most significant bits of a read address, the decoder first encodes the known information symbols by using the corresponding rows of said generator matrix which has already been used to encode the corresponding information word of said information symbols into a codeword and then adds the result giving an intermediate word. Such intermediate word is thereafter subtracted from the received codeword which is to be decoded. The result

is then decoded by a known decoding method using a subcode generator matrix comprising only that part of the generator matrix used for encoding the information word which corresponds to the unknown information symbols, i. e., from the generator matrix used for encoding, the rows corresponding to the information symbols known a priori to the decoder are omitted, and the decoder does only use the remaining rows of the generator matrix as a subcode generator matrix for decoding the result of said subtraction. This means that in the subcode generator matrix only the rows of the generator matrix appear that do not correspond to the a priori known information symbols.
When selecting the generator matrix as described above the error correction power can be enhanced if some information symbols are known to the decoder prior to decoding. There may be different levels of improvement depending on which and how many information symbols are known to the decoder.
A preferred embodiment of the invention is given in claim 2. According to this embodiment the generator matrix of the code comprises at least two subcode generator matrices all having different number of rows wherein all rows of such subcode generator matrices are part of said generator matrix, i.e. the subcodes deriving from said subcode generator matrices are nested in said code deriving from said generator matrix. Each row of the generator matrix can also be regarded as representing a polynomial each having a certain number of zeros. According to the present embodiment certain zeros are common to each polynomial, i. e. to each polynomial represented by one row of the generator matrix. However, each polynomial differs from each other polynomial in at least one zero. With this embodiment it can be achieved that the Hamming distance increases with the number of information symbols known a priori to the decoder.
The generator matrix may also be selected such that its error correction capacity increases with an increasing number of information symbols which are a priori known to the decoder. The generator matrix may further be selected such that the Hamming distance of all proper subcodes of said code generated by some, but not all, rows of the generator matrix is larger than the Hamming distance of said code. This has the advantage that already in the case where one information symbol is known a priori to the decoder the code has an improved error correction capacity no matter which information symbol is known a priori.
Further preferred embodiments of the method of selecting said generator matrix are defined in claims 3 to 6. A method of encoding information words into codewords according to the invention is defined in claim 7; preferred embodiments thereof are given in

claims 8 to 11. A method of decoding possibly mutilated codewords into information words according to the invention is defined in claim 12; preferred embodiments thereof are given in claims 13 to 18.
The method for decoding a possibly mutilated codeword according to the invention is generally characterized in that said information words are encoded into said codewords using a generator matrix selected according to the invention and that the contribution of said at least one a priori known information symbol included in said possibly mutilated codeword is taken into account for decoding said possibly mutilated codeword with enhanced error correcting capabilities. In a preferred embodiment the contribution of said at least one a priori known information symbol included in said possibly mutilated codeword is subtracted from said possibly mutilated codeword before decoding said possibly mutilated codeword.
A preferred embodiment of the invention is based on code puncturing. Therein a larger intermediate generator matrix is used to encode the information words into intermediate codewords having a greater length than codewords encoded using the normal generator matrix. From these intermediate codewords, however, some symbols are omitted to obtain the final codewords. During decoding a received possibly mutilated codeword is first extended by use of the a priori known information symbols to obtain a pseudo codeword which is then decoded using said intermediate generator matrix used during encoding. The obtained second pseudo codeword is thereafter input into an error and erasure decoder, preferably of a known construction, retrieving the information word.
One main advantage of this embodiment is that a larger minimum Hamming distance can be achieved irrespective if the information symbols known a priori are known in a successive order or not. Even if the information symbols are not known successively the minimum Hamming distance of a subcode can be increased by each additional known information symbol if the generator matrix is selected and used according to this embodiment of the invention.
An advantageous application of the present invention lies in the field of address retrieval, in particular on optical media. When using the invention an address or timing information can be protected by a higher error correction capacity making an address retrieval more secure and accurate. The invention can further be used for securing address information in a serial data stream, which is for example transmitted over a transmission line like a telecommunication system or the internet. In general, the invention can be used for

protecting information by a code having an improved - compared to known codes - error correction capacity if part of the information is known a priori to the decoder.
An apparatus for encoding information words and an apparatus for decoding a possibly mutilated codeword according to the invention are defined in claims 23 and 24. It shall be understood that these apparatuses can be developed further and can have similar embodiments which have been explained above with reference to the method of selecting a generator matrix according to claim 1.
A computer program according to the invention for implementing any or all methods according to the invention is defined in claim 25,
A data canier according to the invention is defined in claims 26 and 27. Such a data carrier is preferably used for storing audio, video or software data and might of a recordable or rewriteable type, in particular an optical record carrier like a CD or a DVD. A particular application lies in the field of digital video recording (DVR). Generally, such a data carrier comprises system data items, in particular system data items of address data, timing data or position data, which are already recorded on the data canier at the production site of the data carrier and which are akeady present an empty data carrier for recording user data is bought. The invention may thus be used for encoding said system data items. However, the invention may as well be used for encoding user data.
Still further, a signal for transmitting user data, said signal including system data items, e.g. position, address or timing data, encoded by a method according to the inventions is defined in claim 28.
The invention will now be further explained in more detail with reference to
the drawings, in which:
Fig. 1 shows the conventional format of a codeword.
Fig. 2 shows a block diagram of the encoding and decoding scheme,
Fig. 3 shows an apparatus for encoding information words according to the
invention,
Fig. 4 shows an apparatus for decoding according to the invention,
Fig. 5 shows another embodiment of an apparatus for encoding according to
the invention,
Fig. 6 shows still another embodiment of an apparatus for encoding according
to the invention,

Fig. 7 shows an embodiment of an apparatus for decoding according to the invention,
Fig. 8 shows means for extracting information symbols from a codeword used in the apparatus for decoding shown in Fig. 7,
Fig. 9 shows still another embodiment of an apparatus for encoding according to the invention, and
Fig. 10 shows a corresponding apparatus for decoding according to the invention.
Fig. 1 shows the typical scheme of codewords c of a [n, k] block code, e.g. a Reed-Solomon-Code. A codeword comprises an information word m comprising k information symbols and a parity word p comprising n-k parity symbols generated when encoding said information word m into a codeword c.
Fig. 2 shows a block diagram of a typical system using encoding and decoding. Therein user data, e.g. audio or video data, coming from a data source 1, e.g. recorded on a master tape or master disk, are encoded before they are stored on a data carrier, e.g. a disk, or transmitted over a transmission channel, e.g. over the internet, before they are again decoded for forwarding them to a data sink 9, e.g. for replaying them.
As can be seen the user data of the source 1 are first encoded by a source encoder 2, then error correction encoded by an ECC encoder 3 and thereafter modulated by a modulator 4, e.g. an EFM modulator, before the encoded user data - the codewords - are put on the channel 5 on which errors may be introduced into the codewords. The channel 5 shall here interpreted broadly, including a transmission channel as well as storage of the encoded data on a data carrier for a later replay.
When replay of data is intended the encoded data first have to be demodulated by a demodulator 6, e.g. an EFM demodulator, before they are error correction decoded by an ECC decoder 7 and source decoded by a source decoder 8. Finally the decoded user data can be input to the sink 9, e.g. a player device for replay of the user data.
Such a general system is, however, not only used for encoding and decoding user data, but may as well be used for any kind of data like management data, in particular address data. Such address data are used to find a certain location on a data carrier or in a data stream of user data. On recordable or rewriteable disks such address data are generally prerecorded on the empty disks before any user data are recorded.

The present invention refers to encoding and decoding of data. Therein a certain predetermined generator matrix is used the selection of which is also referred to by a method according to the invention. A particular application of the invention lies in the field of address retrieval of addresses used on optical record carriers.
Fig. 3 shows an embodiment of an apparatus for encoding information words m according to the present mvention. Therein the encoding apparatus 10 comprises an encoding unit 11 for encoding the information words m comprising a fixed number of information symbols m1, m2,..., mk into codewords c of a code C. To achieve an improved error correction capacity a certain predefined generator matrix G is used for encoding the information words m. This generator matrix G is selected and defined once by a selection unit 12 and then provided or preferably stored in the encoding apparatus 10 and the decoding apparatus for continuous use. By use of the generator matrix G the information words m are thus encoded into codewords c by the encoding unit 11. These codewords c can be provided to a writing unit 13 recording the codewords c on an optical record carrier 14, e. g. on a CD or a DVD.
By way of an example the invention, in particular a preferred selection of the generator matrix G, shall be explained in more detail. The example is based on the [7,4, 3] binary Hamming code C generated by g(x) = x3 + x + 1. At first the "normal" known use of the code shall be explained while thereafter the use of a code according to the invention shall be explained.

having four (in general k) rows and seven (in general n) columns. An information word m = (m1, m2, m3, m4) is mapped onto the codeword c = m • Gsys. If the i-th information symbol mi
is known to the decoder prior to decoding, the decoder can subtract the contribution of m1 to the received word r prior to decoding. This means that the decoder decodes the residual received word r - mj • Gsys1 where Gsys1 indicates the i-th row of Gsys, to a code where the i-th row is removed from the generator matrix Gsys- The knowledge of up to any three information bits does not alter significantly the correction capacity for the unknown

information bits, since almost all subcodes C' of the code C obtained by deleting at most three rows of Gsys still have Hamming distance three. Only if the information bits m1, m3 and m4 are known, the Hamming distance for retrieving m2 is increased to four.
According to the present invention, another generator matrix G,d for the same

If the (non-systematic) generator matrix G1d is used for the encoding of the code C, an informed decoder as shown in Fig. 4 can decode to more favourable subcodes C of the code C if certain infonnation bits or information symbols - an information symbol may comprise more than one bit - are known. For example, if the decoder knows the first information bit mi it can use the subcode C generated by the last three rows ga, g3, g4 of Gid, which corresponds to a [7, 3,4] simplex code. As another example, if the last three bits m2, m3, m4 are known to the decoder, it can exploit the subcode generated by the first row of G1d which corresponds to the [7,1,7] repetition code, thus enabling the decoder to recover m1 reliably even in the presence of three bit errors.
An apparatus for decoding a read possibly mutilated codeword r is shown in Fig. 4. Therein the decoding apparatus 20 receives the possibly mutilated codeword r which has been read from the data carrier 14 by a reading unit 21. Assuming that an infonnation word m encoded in a codeword c comprises four information symbols m1, m2, m3, m4 and assuming further that the apparatus 20 for decoding a priori knows three information symbols m2, m3, nu, in a first step said known information symbols m2, m3, nu are encoded by anencoding unit 22 using the generator matrix G which is stored in the encoding apparatus 20 in a storage unit 23 and which had already been used for encoding the codewords c which are stored on the data carrier 14 and read as possibly mutilated codewords r. For such encoding the encoding unit 22 uses the rows of the generator matrix G which correspond to the known information symbols m2, m3, m4.
In a subsequent step the result of such encoding, i.e. the products of the known information symbols m2, m3, m4 with their corresponding rows g2, g3, g4 of the generator matrix G1d, are added by a summing unit 24 giving an intermediate word s. In a subtracting unit 25 the intermediate word s is subtracted from the read codeword r, and the result of such

subtraction is provided to a decoding unit 26. Therein the subcode C which is generated by using a subcode generator matrix G' is decoded wherein the subcode generator matrix G' derives from the generator matrix G in the forming means 27 by omitting all rows from the generator matrix G which correspond to the known information symbols m2, m3, m4, i.e. in the present example by omitting the rows ga, ga, g4. So in the present example, the subcode generator matrix G' does only comprise the first row g1 of the generator matrix G. As a result the unknown information symbol m1 can be retrieved such that the complete information word m is finally known. In general, thus the contribution of said a priori known information symbols included in the possibly mutilated codeword is subtracted from said possibly mutilated codeword, and the result of said subtraction is decoded.
The method of decoding shall now be explained in more detail by way of an example. The codewords c of a code C shall be given by

In general the generator matrix G comprises k rows and n columns, the information word m comprises k columns and a codeword c comprises n columns.
Assuming now that the information symbols ma, ms, nu are known a priori to a decoder and that a read codeword r is given by the sum of the stored codeword c plus an additional noise n the intermediate word s is first computed as

Thereafter a difference between the read possibly mutilated codeword r and the intermediate word s is calculated as:

Therein the information symbol m1 can only be 0 or 1 if the information symbol mi comprises one bit, the row g1 of the generator matrix G is fixed and the noise n is unknown. Using now the above given generator matrix Qd selected according to the invention gi is given as (1 11 1 11 l)such that m1 g1 can only be (0000000) or (1 11111 1). If the before mentioned calculation of m1 g1 + n has for example resulted in (0 0 1 0 0 1 1) the probability will be higher that m1 g1 is given as (0 0 0 0 0 0 0) leading to the result that m1 has bit value 0. As can be seen from this example the information symbol m1 can be

detennined despite three bit errors in the read codeword which means that the remaining subcode C has Hamming distance seven. .
The invention can also be illustrated by way of a simple example which may be used for a fast reliable address retrieval. Conventionally, a [7,4,3] binary Hamming code is generated by the generator polynomial g(x) = x3 + x + 1. Each codeword is a binary polynomial multiple of the generator polynomial g(x). If a systematic encoder is used the information bits appear un-altered in the high order positions, while the parity bits are in the low order positions.
Below, a list of all 16 codewords of the code is given wherein the coefficients of each codeword polynomial are given as a vector. The highest order symbol c6 is at the left, while the lowest order symbol CQ is at the right hand side of each codeword. The four left most bits c6.. .c3 correspond to the four information bits mj.. .mi, and the three right most bits C2, C1, C0 are the parity bits p3, p2, p1. By inspection, it can be checked that any two codewords differ in at least three positions, which means that the Hamming distance of the code equals three so that one error can be corrected:

As an example, the fifth codeword from the top equals 1 • g(x) (in polynomial notation), the fourth codeword from the top equals x • g(x) and the tenth codeword from the top equals x2 • g(x). Important to know is that the (mod 2) sum of any two codewords is
again a codeword, because this is a linear code over GF(2), i. e., the code forms a group. Each information bit is protected against one bit error, and any knowledge about some information bits does not increase the correction capacity of the other information bits.
According to the present invention the mapping of information bits into codewords is changed such that knowledge about at least one, in the given example of three, information bit increases the correction capacity for the remaining, in the example the forth, information bits. In the following the three left most information bits nu, ms, m? may be called the MSB (Most Significant Bits) of an address, and the last information bit mi may be called the LSB (Least Significant Bit) of an address. The code construction according to the present invention is such that, if MSB is known, a strong code for extracting LSB is achieved. If none of the information bits is known a priori the error correction capacity is not changed compared to the error correction capacity of the conventional code.
According to the invention use is made of the linearity of the code. For the encoding of MSB simply those systematic codewords in the above table are used that have m1 = 0. It is to be noted that there are indeed 8 of those codewords. If c (MSB) is the result of this encoding, in order to also encode LSB, c (LSB = 0) = 0000000 and c (LSB = 1) = 1111111 is chosen. The final codeword c that is transmitted equals c = c (MSB) + c (LSB), where the "+" indicates a vector addition over GF(2). It is to be noted that c again belongs to the code (die table) because of the linearity of the code (over GF(2)). It is further to be noted that the effect of adding c (LSB) to c (MSB) scrambles the value of MSB, i. e. if LSB = 1, the values of MSB are inverted. So the overall code is not systematic anymore in all its information bits.
If such a codeword c is transmitted via some channel bit errors may be introduced in the codeword. A received codeword may thus be mutilated and will be called possibly mutilated codeword r which deviates from the codeword c in the error positions. If nothing is known about the information bits, it is only known that the transmitted codeword c belongs to the Hamming code, so that always one bit error can be corrected. After error correction which supposedly restores the codeword c from the received word r the information can be retrieved by first extracting LSB (the information symbol m1) which equals the fourth bit in the codeword c, and with the given LSB either (0 0 0 0 0 0 0) or (1 1 1

1 1 1 1) is subtracted from the codeword c dependent on LSB = 0 or LSB = 1, respectively. Thereafter, MSB is available as the first three bits of the result. If there is more than one transmission error, there will, however, be made errors in the decoding result which always happens with a single error correction Hamming code.
Suppose, however, that MSB is known before decoding, First, the most significant part c(MSB) of the codeword is reconstructed by the decoder and thereafter subtracted from the received word r. Then either (0 0 0 0 0 0 0) or (1 1 1 1 1 1 1) is left, still corrupted by the channel errors. Because the distance of these two words equals 7, LSB can be found even in the presence of 3 bit errors. Thus, by using only three parity bits for the overall code, LSB is effectively protected by a [7,1, 7] repetition code if MSB is known. In this example the [7,4,3] Hamming code is divided into a [7,1,7] subcode and co-sets of this code.
As already explained the invention may be used for protecting addresses which are used on optical record carriers. However, the invention may also be used for protecting addresses in any serial data stream which may also be transmitted over a transmission line. In general, the invention may be applied in any application where information words shall be encoded into a code and where an improved error correction capacity shall be achieved if at least one information symbol is known a priori to the decoder.
In more general terms the invention may be applied to any linear code, in ' particular Reed Solomon codes. A [n, k, n-k+1] RS code can be subdivided into multiple subcodes such that if the j most significant information symbols are known, the effective distance for decoding the remaining k-j information symbols equals n-k+l+j. The decoding procedure also consists of re-encoding the j known information symbols, subtracting the result of this re-encoding from the received word and use the appropriate decoder for I decoding the high distance subcode that is left.
In another embodiment of the present invention the generator matrix G can be selected such that at least two subcodes are nested in the code generated by said generator matrix G. This shall be illustrated by way of the following example. According to the invention the generator matrix G shall be selected as G = (g1(x) g2(x) gaCx))T wherein I

where a is an element in GF(8) satisfying a3 = 1 + a. The corresponding generator matrix thus results in

The codewords c(x) of the code C are therefore polynomial multiples of the generator polynomial g3Cx). The code C generated by this generator matrix G thus has minimum Hamming distance three as will be clear from the above mentioned reference of R. Blahut at section 7.2.
Assuming that the information symbol ma of an information word m = (nii ma m-i) is known a priori to the decoder the subcode Ca" generated by the corresponding subcode generator matrix 02" = (gi g2)^ and having minimum Hamming distance four can be employed. In such subcode C2' all codewords are combinations of the generator polynomials g1 and g2.
If the information symbols mz and m3 are known the subcode C1 generated by the subcode generator matrix G1 = (gi) and having minimum Hamming distance five can be employed.
In addition with the above selection of the generator matrix G less muItiplications are required for the calculation of the codewords c = m G since some of the generator polynomials are polynomial multiples of other generator polynomials.
As can be seen from the above example the subcodes C1 and C2' are nested in the code C and each subcode C1 C2' is generated by a corresponding subcode generator matrix G1 G2'. Each of said subcode generator matrices G1, G2' has a different number of rows wherein all rows are part of said generator matrix G. In general the selection of G can be such that each subcode generator matrix includes an increasing number of rows and each subcode generator matrix can be achieved from the another subcode generator matrix by omitting one row. In the above example the subcode generator matrix G1 derives from the subcode generator matrix G2' by omitting the second row, i. e. by deleting the generator polynomial g2(x). The subcode generator matrix G2' derives from the generator matrix G by deleting the last row of G, i, e. by deleting the generator polynomiar g3(x).

The generator matrix G can also be selected such that the first i rows, i being an integer number equal to or larger than l,.fonn a subcode generator matrix G1 for obtaining a subcode Ci' wherein the Hamming distance is larger than for a subcode Q1 obtained from a subcode generator matrix G1+1which is formed by the first i+1 rows of said generator matrix G.
In more general terms the code C can be an RS code over
GF(q) with generator polynomial .

wherein a is a primitive element in GF(q). The codewords of the code C are represented by polynomials c(x) of degree at most n-1 which are polynomial multiples of the generator polynomial gk(x). According to the invention it is proposed to encode the information symbols mo, mi,..., mt.i into

The information word m is thus encoded with a generator matrix G for which the j-th row consists of the coefficients of the polynomial gj(x). The w top rows of the generator matrix G represent the polynomials gi(x), g2(x), ..., gw(x), all of which are multiples of gw(x). Consequently, these top w rows generate an [n, w, n-w+1] residual code. Hence, if the decoder is informed about (mw, ..., mk-i), then it can correct up to 0.5 (n-w) errors, using a decoder for the RS code with generator polynomial gw(x). It is to be noted that the residual codes for consecutive w's are nested subcodes of the original RS code C,
Another efficient encoding method consists of the following steps. At first the first codword parameter c'(x) is initialized by c\x) = mi. Thereafter for j=2 to k the subsequent codeword parameters c(x) are computed by

Finally, the codeword polynomial c(x) is computed by

The coefficients of said codeword polynomial c(x) together form the codeword

Another preferred embodiment of the invention shall now be explained with reference to Figs. 5 to 8. In Figs. 5 and 6 two embodiments of an encoding apparatus according to the invention for frequency domain encoding, in Fig. 7 a corresponding decoding apparatus is shown, and in Fig. 8 an extracting unit which is part of the decoding apparatus of Fig. 7 is shown in more detail.
Frequency domain encoding and decoding shall be explained by way of the detailed example in the field of digital video recording (DVR). In the example an address information comprising 5 address symbols and 1 auxiliary symbol, together forming 6 information symbols, shall be encoded into a wobble code stored in a wobble signal. In the particular example a [11, 6,6] Reed-Solomon-like code over a Galois field GF (16) shall be used wherein a as a primitive element. The codewords c are thus of the form c(x) = C0 + c1x
The 6 information symbols (also called user symbols) shall be labeled as m5, m6..., m10 i- e. symbols mo to m4 are not used in this particular example. A generator polynomial g(x) is given as

If no information symbol is known to the decoder said code has a minimum Hamming distance of six. However, if information symbol ms is known the minimum Hamming distance is increased by one. With each additional successive information symbol known to the decoder also the minimum Hamming distance is increased by one.
Before implementing the encoding rule several definitions have to be made which will be explained in the following. A parent generator polynomial g(p)(x) is defined by

The coefficients of said codeword polynomial c(x) then form the codeword c in the code C.
The implementation of this encoding rule using a feed forward register is shown in Fig. 5. As can be seen therein in a first portion the information symbols m5 to m10 are at first multiplied with certain parameters, fed to respective feedback shift registers and then summed up. Thereafter the sum is inputted to the feed forward shift register including the coefficients of the parent generator polynomial to form the codeword polynomial c(x).
The general definitions for implementing a frequency domain encoding of an information word m comprising k information symbols mn-k. nin-k+i,..., nin-i into a codeword of an [n,k,n-k+l] Reed-Solomon code over GF(q) are as follows: The parent generator polynomial (g(p)(x)) is given as

The difference between the encoding rules of Figs. 5 and 6 is that in the encoding rule of Fig. 6 the information symbol mn is directly used and that the encoding method implemented in the apparatus of Fig. 6 is a hybrid method of frequency and time domain encoding while the encoding method implemented in the apparatus of Fig. 5 is a method for pure frequency domain encoding.
The general definitions for implementing the hybrid encoding of an information word m comprising k information symbols ma-k, nin-k+i,..., ma-1 to a codeword of an [n,k,n-k+l] Reed-Solomon code over GF(q) are as follows: The parent generator polynomial (g(t)(x)) is given as

in common. Therefore the following properties of the parent and the component generator polynomials can be used for the extraction of the information symbols:

A corresponding decoding apparatus is shown in Fig. 7. Therein it is assumed that a received word r(x) comprising symbols ro, ri,..., tn is a possibly mutilated codeword, i. e. includes a codeword c plus noise n. From the received word r syndromes Sj are computed according to a known method in a syndrome forming unit 30 wherein it holds that

A detailed embodiment of said extracting unit 33 is shown in Fig. 8.
As shown before, the Hamming distance of the described code increases to kmax + 2 if information symbols ms, mg,.,., mkmax are known thus enabling a more reliable address recognition. The increase in Hamming distance does not cost an extra redundancy and the decoder of the code might be a usual decoder which is capable of computing some extra syndromes. Knowledge of some information symbols thus allows to update and subsequently use the syndromes corresponding to these information symbols.
In more general terms the syndromes Sj are computed by

Yet another embodiment of the invention based on code puncturing shall now be expl^'ned with reference to Figs. 9 and 10. Fig. 9 illustrates the method of encoding an information word m into a codeword c and Fig. 10 illustrates the method of decoding a possibly mutilated codeword r into an information word m.
As shown in Fig. 9 the information word m comprising k information symbols is encoded by an encoding unit 41 of an encoding apparatus 40 using an intermediate generator matrix C. Said intermediate generator matrix G"derives from a generator matrix G which has been selected by a selection unit 42. The intermediate generator matrix G' is larger than the generator matrix G in that it comprises at least one more column than the generator matrix G. In general, the generator matrix G has k rows and n columns while the intermediate generator matrix G" has k rows and n+k columns and comprises k columns with a single non-zero entry at mutually different positions. When using said intermediate -generator matrix G' for encoding the information word m, intermediate codewords t having k + n symbols are obtained. From said intermediate codeword t the codeword c is obtained from a codeword generating unit 44 by omitting a number of symbols of said intermediate codeword t. Therein the number of symbols to omit corresponds to the difference between the number of columns of said intermediate generator matrix G' and said generator matrix G. Thus, the obtained codeword c comprises n symbols.
During decoding a possibly multilated codeword r comprising n symbols is received by a decoder as shown in Fig. 10. In a first step the received word r is extended into a first pseudo codeword r' by an extension unit 50. Therein said intermediate generator matrix G'" which has already been used in the encoder is used to determine the length of said

pseudo codeword r', i. e, the number of symbols of said pseudo codeword r' corresponds to the number of columns of said intermediate generator matrix C, i. e. to the n symbols of the received word r k erasures are added to obtain the pseudo codeword r'.
Thereafter, in a replacement unit 51a priori known information symbols, e.g. m1, m5, m6, are replaced in said pseudo codeword r" at positions of the erasures which correspond to the positions of said a priori known information symbols. This means that the erasures 1, 5 and 6 are replaced by the a priori known information symbols m1, m5, m6. The obtained second pseudo codeword r' is thereafter inputted to a decoder unit 52 which is preferably a known error and erasure decoder decoding said second pseudo codeword r' by use of said intermediate generator matrix G" into the information word m comprising k symbols.
According to this embodiment of the invention a larger intermediate generator matrix G" is used compared to other embodiments of the invention. However, the advantage of this embodiment is that the information symbols do not need to be known a priori in successive order but any additional information symbol known a priori irrespective of the position of the information symbol within the information word generally leads to an enhanced minimum Hamming distance compared to the code used if no information symbols

The rightmost 5 columns of the intemiediate generator matrix C are used as a generator matrix G, i. e, the generator matrix G is

The code generated by the generator matrix G has minimum Hamming distance 3. Knowledge of any j information symbols effectively increases the minimum Hamming distance from 3 to 3 + j.

CLAIMS:
1. Method of selecting a generator matrix (G) for encoding information words (m) comprising information symbols (m1, m2,..., mk) into codewords (c) of a code (C) for providing an enhanced error correction capability if at least one information symbol (m1, m2, m3) is known a priori to a decoder decoding received, possibly mutilated codewords (r), characterized in that said generator matrix (G) is selected such that the minimum Hanuning distance of at least one subcode (C) of said code (C) is larger than the minimum Hamming distance of said code (C) and that a subcode generator matrix (G') of said subcode (C') derives from said generator matrix (G) of said code (C) by omitting the at least one row from said generator matrix (G) corresponding to said at least one a priori known information symbol (m1 m2, m3).
2. Method according to claim I, characterized in that said generator matrix (G) is selected such that there are at least two subcodes (C1' C2', C3') of respectively increasing Hamming distance, that said subcodes (C1' C2', C3') are nested in said code (C) and that each subcode (C1' C2', C3') is generated by a corresponding subcode generator matrix (G1 G2', G3'), wherein each subcode generator matrix (Gi', G2', G3') has a different number of rows and all rows are part of said generator matrix (G).
3. Method according to claim 2, characterized in that said subcode generator matrices (Gi', G2', G3') include an increasing number of rows, wherein the number increases by one for each generator matrix (G1', G2', G3') and wherein the (i-l)-th subcode generator matrix (Gi') derives from the i-th subcode generator matrix (G2O by omitting one row.
4. Method according to claim 3, characterized in that said generator matrix (G) is selected such that for all integer numbers i, i being an integer number equal to or larger than
1 but at most k-1 where k is the number of rows of said generator matrix (G), a number of i
rows forms a subcode generator matrix (G1') for obtaining a subcode (C1) having a larger
Hamming distance than a subcode (C1+1) obtained from a subcode generator matrix (G1+1)
I formed by a number of i+1 rows of said generator matrix (G).

5. Method according to claim 1, characterized in that said generator matrix (G)
derives from a larger, intermediate generator matrix (G"), which has at least one column
more than said generator matrix (G) and which generates a code having an increased
minimum Hamming distance, by omitting said at least one column having a single non-zero
entry.
6. Method according to claim 5, characterized in that said generator matrix (G)
has k rows and n columns, that said intermediate generator matrix (G"), having k rows and
n+k columns, comprises k columns each with a single non-zero entry at mutually different
positions and that said generator matrix (G) derives from said intermediate generator matrix
(G") by omitting said k columns.
7. Method of encoding information words (m) comprising information symbols
(mu m2, ...,mk) into codewords (c) of a code (C) for providing an enhanced error correction
capability if at least one information symbol (mu mi, ma) is known a priori to a decoder
decoding received, possibly mutilated codewords (r), characterized in that a generator matrix
(G) selected according to a method of claim 1 is used for encoding said information words
(m) into said codewords (c).

9. Method according to claim 7, wherein an information word (m) comprising k
information symbols (mn-k, mn-k+i, -., mn-i) is encoded to a codeword (c) of an [n,k,n-k+l] Reed-Solomon code over GF(q), said encoding comprising the steps of: a) defining a parent generator polynomial (g^^^(x))

wherein a is a non-zero element of GF(q) of order at most n, and b is an integer number;
ci c) computing thie codeword polynomial (c(x))

wherein the coefficients of said codeword polynomial (c(x)) form the codeword (c) in the
code (C).
10, Method according to claim 7, wherein an information word (m) comprising k infonnation
symbols (mu-k.nia-ic+b ..., mn-i) is encoded to a codeword (c) of an [n,k,n-k+l] Reed-Solomon
code over GF(q), said encoding comprising the steps of:
defining a parent generator polynomial (g(i)(x))

wherein a is a non-zero element of GF(q) of order at most n, and b is an integer number;
b) defining component generator polynomials (g^^^) for n-k
c) computing the codeword polynomial (c(x))

wherein the coefficients of said codeword polynomial (c(x)) form the codeword (c) in the code (C).

11. Method according to claim 7, wherein a generator matrix (G) selected
according to a method of claim 5 and derived from an intermediate generator matrix (G") is
used for encoding said information words (m) into said codewords (c), comprising the steps
of:
a) generating intermediate codewords (t) by encoding said information words (m) using said intermediate generator matrix (G"),
b) generating said codewords (c) from said intermediate codewords (t) by omitting at least one symbol, wherein the number of symbols to omit corresponds to the difference between the number of columns of said intermediate generator matrix (G") and said generator matrix (G).
12. Method of decoding possibly mutilated codewords (r) of a code (C) into
infonnation words (m) comprising information symbols (m1, m2, ...,nik), said information
words (m) being encoded into codewords (c) of said code (C) using a generator matrix (G)
and said code (C) being provided with an enhanced error correction capability if at least one
information symbol (m1, m2, m3) is known a priori before decoding, characterized in that said
information words (m) are encoded into said codewords (c) using a generator matrix (G)
selected according to a method of claim 1 and that the contribution of said at least one a
priori known information symbol (m1, m2, m3) included in said possibly mutilated codeword
(r) is taken into account for decoding said possibly mutilated codeword (r) with enhanced
error correcting capabilities.
13. Method according to claim 12, comprising the steps of:
a) encoding said a priori known information symbols (m1, m2, m3) using the corresponding rows of said generator matrix (G) of said code (C),
b) adding the results of the encoding step representing an intermediate word (s).
c) subtracting said intermediate word (s) from said possibly mutilated codeword (r) to be decoded,
d) decoding the result of said subtraction by a known method for decoding the code generated by the rows of the generator matrix (G) that do not correspond to said a priori known information symbols, and
e) recovering the information word (m).

14. Method according to claim 12, comprising the steps of:
a) forming syndromes (S) from, a received, possibly mutilated codeword (r),
b) fonning additional syndromes (S') using said a priori known information symbols (m5, m6,..., mmax) and said possibly mutilated codeword (r),
c) calculating the information word (m) using said syndromes (S) and additional
syndromes (S').
15. Method according to claim 14, wherein the information word (m) is calculated by the
steps of
cl) calculating error locations and error values using said syndromes (S) and
additional syndromes (S') to obtain the codeword (c), and
c2) extracting the information word (m) from said obtained codeword (c).

wherein ma-k,ma-k+i,...,niQ.k+s.i are the known a priori infonnation symbols and wherein said information words (m) are extracted from said obtained codewords by mj = 0(0^"*"*') for n-k ^ j 18. Method according to claim 12, wherein a generator matrix (G) selected
according to a method of claim 5 and derived from an intermediate generator matrix (G') is
used for encoding said information words (m) into said codewords (c) according to a method
of claim 11, comprising the steps of:
a) extending said possibly mutilated codeword (r) to a pseudo codeword (r') by adding erasures at positions corresponding to said columns that have been omitted in said intermediate generator matrix (G") to obtain said generator matrix (G),
b) replacing the erasures at positions corresponding to said a priori known information symbols (m1, m2, m3) by said a priori known information symbols to obtain a second pseudo codeword (r"), and
c) decoding said second pseudo codeword (r') by a known method for error and erasure decoding of a code generated by said intermediate generator matrix (G")-

19. Method according to any one of claims 1, 7 and 12, characterized in that said infonnation words (m) comprise data items wherein successive information words have predetermined corresponding data item elements such that knowledge of a first information word comprising a first data item leads to knowledge of data item elements of one or more successive data items included in subsequent information words,
20. Method according to claim 19, characterized in that said information words (m) comprise address information, in particular address information of positions in a serial data stream and/or of positions on a data carrier.
21. Method according to claim 20, characterized in that said method is applied in digital video recording for encoding an address information into a wobble code to be stored on a data carrier in a wobble signal.
22. Method according to claim 20, characterized in that said information words (m) of said address information comprise multi-bit information symbols.

23. Apparatus for encoding infonnation words (m) comprising information
symbols (mi, ma, ...,mk) into codewords (c) of a code (C) for providing an enhanced error
correction capability if at least one information symbol (m1, m2, m3) is known a priori to a
decoder decoding received, possibly mutilated codewords (r), comprising means for encoding
said information words (m) into said codewords (c) using a generator matrix (G) selected by
a method according to claim 1.
24. Apparatus for decoding possibly mutilated codewords (r) of a code (C) into information words (m) comprising information symbols (m1, m2, m3) , said information words (m) being encoded into codewords (c) of said code (C) using a generator matrix (G) selected by a method according to claim 1 and said code (C) being provided with an enhanced error correction capability if at least one information symbol(m1, m2, m3) is known a priori before decoding, comprising means for taking the contribution of said at least one a priori known information symbol (m1, m2, m3) included in said possibly mutilated codeword (r) into account for decoding said possibly mutilated codeword (r) with enhanced error correcting capabilities.
25. Computer program for implementing a method of claim 1,7 and / or 12.
26. Data carrier for recording user data, said data carrier having stored system data items encoded by a method according to claim 7.
27. Data carrier according to claim 26, wherein said system data items comprise address data and / or timing data used for finding a position on said data carrier.
28. Signal for transmitting user data, said signal including system data items encoded by a method according to claim 7.

29. Method of selecting a generator matrix for encoding information
words substantially as herein described with reference to the
accompanying drawings.
30. An apparatus substantially as herein described with reference to the
accompanying drawings.

Documents:

086-chenp-2003-claims.pdf

086-chenp-2003-correspondnece-others.pdf

086-chenp-2003-correspondnece-po.pdf

086-chenp-2003-description(complete).pdf

086-chenp-2003-drawings.pdf

086-chenp-2003-form 1.pdf

086-chenp-2003-form 18.pdf

086-chenp-2003-form 3.pdf

086-chenp-2003-pct.pdf

« Previous Patent

Next Patent »

Patent Number

229652

Indian Patent Application Number

86/CHENP/2003

PG Journal Number

13/2009

Publication Date

27-Mar-2009

Grant Date

19-Feb-2009

Date of Filing

14-Jan-2003

Name of Patentee

KONINKLIJKE PHILIPS ELECTRONICS N.V

Applicant Address

GROENEWOUDSEWEG 1, NL-5621 BA EINDHOVEN,

Inventors:

#	Inventor's Name	Inventor's Address
1	VAN DIJK, MARTEN, E	PROF HOLSTLAAN 6, NL-5656 AA EINDHOVEN,
2	BAGGEN, CONSTANT, P., M.J	PROF HOLSTLAAN 6, NL-5656 AA EINDHOVEN,
3	TOLHUIZEN, LUDOVICUS, M., G., M	PROF HOLSTLAAN 6, NL-5656 AA EINDHOVEN,

PCT International Classification Number

H03M 13/13

PCT International Application Number

PCT/IB02/01624

PCT International Filing date

2002-05-08

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	01201841.2	2001-05-16	EUROPEAN UNION