Source: http://www.google.com/patents/US7725779?dq=6272333
Timestamp: 2015-04-25 01:29:21
Document Index: 389619050

Matched Legal Cases: ['Application No. 20040085878', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US7725779 - Multi-valued scrambling and descrambling of digital data on optical disks ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsMethod and apparatus for writing scrambled multi-value data to a physical media and for reading scrambled multi-value data from a physical media, are disclosed. The physical media can be an optical disk. The scrambling can be performed by a multi-valued LFSR scrambler and the descrambling can be performed...http://www.google.com/patents/US7725779?utm_source=gb-gplus-sharePatent US7725779 - Multi-valued scrambling and descrambling of digital data on optical disks and other storage mediaAdvanced Patent SearchPublication numberUS7725779 B2Publication typeGrantApplication numberUS 11/042,645Publication dateMay 25, 2010Filing dateJan 25, 2005Priority dateJan 25, 2005Fee statusPaidAlso published asUS8225147, US20060164883, US20100211803Publication number042645, 11042645, US 7725779 B2, US 7725779B2, US-B2-7725779, US7725779 B2, US7725779B2InventorsPeter LablansOriginal AssigneeTernarylogic LlcExport CitationBiBTeX, EndNote, RefManPatent Citations (39), Non-Patent Citations (9), Referenced by (6), Classifications (10), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMulti-valued scrambling and descrambling of digital data on optical disks and other storage media
US 7725779 B2Abstract
Rotating storage media, such as optical disks, may contain operational data used for the correct operation of the medium as a storage device. These data can either be invariant or may be predictive in nature, so that the system can anticipate their presence. These data can be separate and different from user-data. It is important for the system to distinguish between �maintenance/control� data and user-data, or be able to use the �maintenance/control� aspects of user-data. The storage system should not change the information content of user-data. The system may change the user-data's statistical properties, without changing its information content, so it acquires useful system operational properties from the user data.
Tracking and Synchronization Patterns on Multi-Level Storage Disks
Different multilevel symbol storage technologies have already been described for optical disks. Technologies such as �trapped electron� technology (See, U.S. Pat. No. 5,007,037 titled: �Optical disk drive system utilizing electron trapping media for data storage� by Lindmayer, which is hereby incorporated by reference in its entirety) and �phase change� technology (See U.S. Pat. No. 5,136,573, titled �Information recording apparatus and method�, by Kobyashi, which is hereby incorporated by reference in its entirety) disclose technologies for writing and reading multilevel data symbols to and from optical disks. It is understood that an aspect of this invention is concerned with multilevel or multi-value data symbols. These terms mean that each symbol can have one of n states, wherein n is an integer greater than 2. Multi-valued symbols can also be represented by a plurality of binary symbols. In that case the invention may require additional means to synchronize the plurality as a single symbol.
1. U.S. Pat. No. 6,148,428 titled: �Method and Apparatus for Modulation Encoding Data for Storage on Multi-level, Optical Recording Medium� by Welch et al, which is hereby incorporated by reference in its entirety.
2. United States Patent Application No. 20040085878, titled, �Multi-level data processing method and apparatus� by Sakagami et al, which is hereby incorporated by reference in its entirety.
3. U.S. Pat. No. 5,657,014 titled �M=7(3,7) Run Length Limited Code for Multilevel Data� by McLaughlin, which is hereby incorporated by reference in its entirety.
4. United States Patent Application 20040156284, �Method and apparatus for reading and writing a multilevel signal from an optical disc oscillators� by Wong et. al., which is hereby incorporated by reference in its entirety.
In accordance with one aspect of the present invention, multi-value data is written to and read from the optical disk 100. The detected multilevel signal may be processed by an A/D converter 107 to generate binary signals for further processing. According to one aspect of a previous invention by the inventor�realizing n-value logic functions with gates and inverters�it is possible to process all signals with n-valued digital logic functions. In that case an A/D converter is not required.
The reading and writing process may involve other signals (such as clock signals) and mechanisms such as data-buffers and measures to suppress effects such as jitter. While important to the proper working of the operation of the optical disk process, these measures are known and may not be essential to the scrambling and descrambling methods. They are noted and recognized but not shown in the diagrams of FIGS. 1 and 1 a. The data on the disk may be arranged in frames or sectors. One aspect of the correct operation of reading (and writing) the disk is the determination and knowledge of what part of the disk is being read. Pre-determined blocks of data may contain a unique pattern that is used as a synchronization pattern for the control mechanisms and processing of the data.
Synchronization patterns should be unique, so that they will not be confused with �user data�. Its pattern should also allow to sharply and exactly determine the reading position of the drive. In other words, the data reading or writing mechanisms should not make a false decision on where a �user-data sector� starts.
To obtain a picture of the correlation performance of a multi-symbol sequence, one copy of the sequence is phase-shifted one symbol and compared to the original sequence, by determining the correlation value. When the length of a sequence is �p� symbols, this shift and compare is usually done (p−1) shifts to the left, (p−1) shifts to the right and one matching step. The total correlation then contains 2*p−1 individual correlation values.
seq_a
seq_b
K FF ( θ v ) = lim θ → ∞ 1 θ ∫ - θ 2 θ 2 F ( θ ) F ( θ + θ v ) ⅆ θ . (source: page 70 of Transmission of Information by Orthogonal Functions. by Henning F. Harmuth. Springer-Verlag 1972.)
C ( j ) = 1 N ∑ i = 1 N a i a i + j This expression determines the autocorrelation of the function A with N elements ai. For the cross-correlation of two different functions A and B with N elements ai and bi the following expression determines the cross-correlation:
In U.S. patent application Ser. No. 10/935,960 titled �Ternary and Multi-value Digital Signal Scramblers, Descramblers and Sequence Generators�, the inventor has shown as one aspect of his inventions, how to create n-valued m-sequences with n a prime number and using LFSR based sequence generators.
FIG. 4 shows a diagram 400 of the ternary LFSR based sequence generator here used in the example, with a 4 element shift register with elements 403, 404, 405 and 406. A ternary sequence is outputted on 402. The in FIG. 4 applied ternary logic device 401 has a function �ter1� with the following (non-commutative) truth table:
FIG. 5 shows a correlation graph for the sequence outputted on 402 in FIG. 4. The correlation rule used here is �add 1 when symbols are identical� and �subtract 1� when symbols are not equal. The dynamic range of the correlation is from 80 to −28 or over 100. Even when taking into account that the length of the sequence is greater than the previous binary one, it should be clear that the dynamic range in correlation is in general greater for ternary sequences than for binary sequences when the sequences have the same number of symbols. Consequently ternary sequences have better synchronization performance than binary sequences of the same length, or shorter ternary sequences can have an equal or a better synchronization performance than longer binary ones. In general one may conclude that n-valued sequences with good correlation, may show better synchronization performance than p-valued sequences with equal length and good correlation when n is greater than p.
FIG. 6 shows a diagram of a ternary logic circuit that can be used to determine synchronization in accordance with an aspect of the present invention. The signal �sdisk� is the sequence coming from the disk and is provided to a first input 605 a of ternary circuit 601 and to a first input 605 b of circuit 602. The signal �slocal� is the sequence generated (or obtained from a memory device) in the local synchronization logic and is provided to a second input 606 a of circuit 601 and to a second input 606 b of circuit 602. Thus, the circuit of FIG. 6 compares a local synchronization circuit to the signals from an optical disk to determine synchronization. The circuit shown in FIG. 6 may be used in the synchronization circuits 114 and 214 in FIGS. 1 a and 1 b, respectively.
The ternary logic function �ter+� has the following truth table:
ter+
The device 601 with function �ter+� will generate a 1 on output 610 when symbols in sequence �sdisk� and �slocal� are identical. It will generate a 0 on 610 when the symbols are different. The output 610 of 601 provides the generated 0 or 1 of 601 to the adder/control unit 603, which will add an incoming 1 to the total sum, and remain unchanged when a 0 was generated.
The truth table of the ternary logic function �ter−� is shown in the following table.
ter−
The device 602 with function �ter−� will generate a 1 on output 611 when �sdisk� and �slocal� are not equal. It will generate a 0 on 611 when �sdisk� and �slocal� are identical. The output 611 of 602 will provide a 0 or 1 to the adder control unit 603, which will subtract the value of signal coming from 602 from the total sum. The add/subtract unit may be controlled by a clock signal 607. Every clock cycle the new sum is calculated and outputted on output 608, which is also input to decision circuit 604. The decision circuit decides whether synchronization is detected. For example, the decision circuit 604 may decide that synch is detected when the correlation between the signal from the disk and a local signal exceeds a threshold. A reset signal (not shown) will reset the sum when is was decided that no synchronization was achieved. The reset signal is generated after a certain number of clock cycles or after a certain amount of time. Several of these circuits may run in parallel but with clocks shifted whole cycles in phase. The reason for this is that it will take some cycles to determine if a no synchronization situation exists. However during that period the beginning of the actual synchronization sequence may occur and should be identified from the beginning. Different correlation strategies are known and can be applied. One such strategy could be that if the running sum of correlation values is greater than a pre-determined value, then it is certain that two sequences are synchronized. The end of the synchronized sequences may be determined by a known and unique pattern. It is then certain that following this pattern the next data are user-data.
Functions �ter+� and �ter−� can be combined, for instance into a function �ter+−� with the following truth table:
ter+−
When ter+− is used, the device with this function will supply a single output to the circuit 603 e as illustrated in FIG. 6 e. The circuit 603 e is almost identical to 603 in FIG. 6 a. The first difference is that inputs 610 and 611 of FIG. 6 a are now combined to one input 610 e, being the output of a single device with function �ter+−�. Another difference is that a ternary inverter 619 is inserted. This inverter will transform a state 2 into a state 1 signal. However it will change all other states not into 1. So one possible inverter could then be [2 0 1] with changes 0 to 2; 1 to 0 and 2 to 1. The logic of 603 e is now such that a 1 will be added to the sum when the output of the function �ter+−� is 1; a 1 is subtracted from the sum when the output of �ter+−� is 2.
A simpler solution is of course when �ter+−� is identical to �ter+�. This means that a 1 is added to the sum when the signals �sdisk� and �slocal� are identical. Nothing will happen when the signals are different. The range for the correlation for the sequence of the example then varies between 80 and 26. This may be sufficient for synchronization in a situation with limited noise or interferences. This correlation method is realized in the circuit of FIG. 6 b. A dramatic improvement in correlation value range can be achieved in accordance with one aspect of the present invention by creating, what can be called, an �unbalanced� correlation mechanism, meaning adding more than 1 when symbols are identical and subtracting nothing (or for instance 1) when symbols are different. For instance one can add 3 when symbols are identical and subtract 1 when symbols are different. The correlation value will range between 240 and 24 in that case.
The following table shows the dynamic range of different correlation methods for situations with no errors and for situations where a burst of 10 �all equal symbols� occurs within the frame of a synchronization sequence. The ternary sequence used is the 80 chips sequence generated by the circuit of FIG. 4.
Most sequence generators are based on prime numbers GF(n) LFSR based pn-generators. In U.S. Provisional Patent Application No. 60/575,948 titled �Multi-value Coding of Sequences and Multi-value Memory Devices�, the inventor describes as one aspect of multi-valued logic, n-valued pn-like sequences with n being a non-prime number. A 4-valued example will be provided in a later section. The inventor has also developed novel methods to create Gold-like n-valued sequences, with n being prime and non-prime, with very sharp and easy to distinguish correlation peaks and very low cross-correlation. All these and other n-valued sequences generated by LFSR based sequence generators with n-valued logic functions, created from reversible n-valued inverters, can serve very well as synchronization sequences in optical disk and other applications.
This descrambler has two ternary logic functions. The function �ter1�, of which the truth table is shown in the following table.
The descrambler also comprises a function �ter2� of which the truth table is shown in the next table.
The resulting output of the descrambler will be all 1s when the initial content of the shift registers of the sequence generator and descrambler are identical. When the content of the shift registers are not identical, the shift register of the descrambler will be �flushed� in 4 cycles, during which period the output may not be identical to all 1s The output signal of this descrambler will always be all 1s after the first 4 symbols.
By using the following truth table for �ter2� the descrambler can produce an all 0s output.
And by using a function �ter2� with the following truth an all 2s output can be created.
scrambled synchronization sequence
1112112012111200110
descrambled synchronization sequence
0000000000111111111
The scrambler 900 has two ternary logic devices: 903 with function �ter1� and device 904 with function �ter2�. The truth tables of these functions are provided in the following tables.
A signal �descrambled output� is outputted on output 902. It should be clear that the first 4 symbols of the descrambled sequence outputted on output 902 may be different from 0 if the initial content of the shift register is not [0 0 0 0]. However after 4 clock pulses (not shown in the diagram) the shift register is �flushed� and the outputted sequence from then on is identical to the correctly descrambled sequence. Symbolically one may present the descrambled sequence as shown in the following table.
Correctly descrambled
uncertain descrambled
xxxx000000111111111
The �uncertain descrambled synchronization sequence� reflects a situation where the initial content of the shift register was not [0 0 0 0]. It is evident that the descrambled synchronization sequence always has at least 6 0s. These zeros may be used to initiate a counter/adder.
The benefit of using a digital sum for synchronization, based on descrambling a known sequence, is that no sequence comparison technology, including a local copy of the sequence, is required. The digital sum circuit �knows� that after reaching a certain number, the following symbol will be user data.
All of the above synchronization and correlation methods and apparatus can be used in accordance with one aspect of the present invention to generate and detect, ulti-value synchronization signals for use by circuits 109 and 114 in FIG. 1 a and by circuits 209 and 214 in FIG. 1 b. Multilevel Data-Scrambling and Security.
FIG. 13 shows a diagram of different solution, showing segment 1300 as part of a data track on an optical disk. Because the shift register will be �flushed� after 5 clock cycles in the illustrative case using the diagram of FIG. 13, one may create a data-track 1301 of which the first 5 symbols in 1303 right after synchronization sequence 1302 may be ignored. At the 6th symbol the descrambler is generating the correctly de-scrambled user-data.
Another aspect of this invention applies a different approach in scrambling and descrambling. The configuration in FIG. 13 has a security drawback. While easy to operate, because of its �flushing� effect of the shift registers, unauthorized users can try different descramblers, until one will work. With higher value logic it will become statistically more unlikely to find the correct configuration by chance.
2011221021122201221201200001000212112101
1112001012221221121011220120210012121111
2102000222212100210010102101012001022010
1120010122212211210112201202100121211111
2000212211101211102100222222110100022101
The table shows the symbolic representations of sequences of 40 ternary consecutive symbols. Row 1 shows an unscrambled user-data sequence. Row 2 shows the scrambling sequence. Row 3 shows the result of scrambling the sequence of row 1 with the sequence of row 2 with the ternary scrambling/descrambling function �descram�. The scrambled sequence of row 3 can be written as user-data (possibly after error-coding) on a multilevel optical disk.
The sequence as shown in row 3 will be read from the optical disk and (potentially after error decoding) descrambled with a locally available descrambling sequence as shown in row 4 with a device executing descrambling function �descram�. The result is the descrambled sequence as shown in row 5 of the table. The sequences of row 1 and row 5 are identical.
The scrambled sequence and the descrambling sequence are out of phase and inputting the sequences of row 3 and row 6 to the descrambling function �descram� will generate the sequence as shown in row 7 of the table. The sequences of row 1 (the original user-data) and row 7 are clearly different.
One aspect of a previous invention as described in U.S. patent application Ser. No. 10/912,954 titled �Ternary and higher Multi-value Digital Scramblers/Descrambler� is a method to combine different scrambling functions, with different scrambling sequences to create a composite multi-valued data scrambler.
FIG. 15 shows a diagram of a composite scrambler, having k individual scramblers, of which are shown 1501 scrambler_1, 1502 scrambler_2 and 1503 scrambler_k. Each scrambler has a second input providing a scrambling sequence. Scrambler_1 has a second input 1507 providing scrambling sequence �sequence 1�, scrambler_2 has a second input 1508 providing �sequence 2� and scrambler_k has a second input 1509 providing �sequence k�. The first individual scrambler 1501 has external data provided at its first input 1500. The second scrambler 1502 has as its first input 1504, which is also the output of the scrambler 1501. The last scrambler 1503 has as its first input 1505, which is the output of its preceding scrambler. All consecutive individual scramblers (except the first one) have the output of their previous individual scrambler as its first input. The scrambled sequence is outputted on output 1506. The scrambler of FIG. 15 can be used to scramble the data in circuits 209 and 214 of FIG. 1 b. For illustrative purposes it is assumed that the individual scramblers of the composite scrambler all operate within the duration of one symbol, in such a way that within the duration of a symbol, a symbol at the input determines the symbol at the output. No time delay effects are assumed, though to those skilled in the art it will be clear that the system may be adapted to delays, by for instance applying registers or memory elements between the individual scramblers and a relevant clock signal.
The inverter i1 is the identity. Inverters i1, i2, i3 and i6 are self reversing inverters. The columns of the truth table of ternary scrambling function �descram� can be realized with the inverters i6 for its first column, i3 for its second column and i2 for its third column. All columns of the function �descram� can be represented by self-reversing inverters. The function �descram� is a self-reversing ternary function.
FIG. 16 shows an individual scrambler 1600. The individual scrambler 1600 has a first input 1601 providing a user-data sequence which has to be scrambled. The scrambler 1600 also has a second input 1602 providing a known scrambling sequence. The output 1603 of the scrambler provides the scrambled ternary sequence, which can be error-coded, modulation coded and written to an optical disk. The scrambler of FIG. 16 can be used in the circuits 209 and 214 in FIG. 1 b. As another aspect of this invention, the descrambling method will be stored on the disk. This means that without this information, no descrambler is configured at the data reading stage.
The process applied to scramble the user data is shown in the flow diagram of FIG. 17. As an illustrative example the scrambling of a 40 elements ternary sequence is described. First a 40 element ternary scrambling sequence will be determined. This sequence may be stored in a memory for later use, however it can also be generated real-time at the right time if desired. The ternary scrambling function is determined. For the example it is assumed that the choice is between two scrambling functions �scram� and �scram_1� of which the truth tables are shown in the following tables.
The scrambling function �scram� has as its columns the self-reversing inverters i6, i3 and i2. The scrambling function �scram_1� has as its columns the reversible inverters i5, i4 and i1.
The descrambling functions �descram� and �descram_1� that will correspond to descramble a signal scrambled by the functions �scram� and �scram_1� have truth tables that are shown in the following table.
descram_1
The scrambling function �scram� has itself as its descrambler. The function �scram_1� is comprised of inverters i5, i4 and i1 has function �descram_1� with inverters i4, i5, and i1 as its descrambling function.
The three digit ternary code [0 1 1] will be used to designate the scrambler with function �scram� and the ternary code [2 0 2] will be used to designate the scrambler with function �scram_1�. The purpose of this coding will become apparent when explaining the descrambling phase. The three digit code will be replacing the last 3 digits of the scrambling sequence.
A flow diagram for the descrambling process of the scrambled user-data from the disk is shown in FIG. 18. First the scrambling sequence is read from the disk and (including potentially error-correcting decoding) is stored in a memory device. The last 3 elements of the scrambling sequence are used to select and enable the appropriate descrambling device. If the 3-digit code is [0 1 1] the descrambling function is identical to the function �scram�. If the code is [2 0 2] the descrambling function should be �descram_1�.
The next step is to read the scrambled user data from the disk and descramble the scrambled user-data with the scrambling sequence by a device with ternary function �descram_1�.
U.S. patent application Ser. No. 11/000,218 titled �Single and composite Binary and Multi-valued Logic Functions from Gates and Inverters� by the inventor describes in detail multi-valued gates and inverters, and is hereby incorporated by reference in its entirety.
FIG. 19 shows a diagram of a circuit 1900 which can descramble the user-data. The scrambling-sequence 1901 of 40 elements is read from the disk and put in a memory element. Such a memory device could be a binary memory device, representing the ternary symbols as 2 bit binary words, combined with appropriate A/D and D/A converters. It can also be a truly ternary memory device as described in U.S. Provisional Patent Application No. 60/575,948 titled �Multi-value Coding of Sequences and Multi-value Memory Devices� and in U.S. Provisional Patent Application No. 60/599,781 titled �Multi-valued digital information retaining elements and memory devices.�
The last three elements 38, 39 and 40 of the scrambling sequence can be put in a dedicated 3 element memory device 1902. The first element of this memory device is called c1 and its content is outputted on 1903, the second element is c2 and its content is outputted on 1904 and the third element is c3 and its content is outputted on 1905. When the user-data is scrambled by function �scram� the applied code, and consequently the values of [c1 c2 c3] is [0 1 1]. When the scrambling function was �scram_1� the content of [c1 c2 c3] is [2 0 2].
The descrambling circuit 1900 is comprised of 6 branches containing inverters and 2 individually controlled gates. The first branch will be described in detail. It contains an inverter 1910, with function i6. A first individually controlled gate 1907 in this and each other branch is controlled by a signal �b�, representing the current element of the scrambling sequence 1901 outputted on 1906. The output 1906 which provides the current read element of the scrambling sequence 1901 is connected to all control inputs of the first gates in each branch.
As an example an individually controlled gate 1914 is shown in diagram as a circle with inside the circle a horizontal line and a number. The horizontal line means that the gate is conducting for a certain control signal provided by its control input 1915. The control signal for which the gate is conducting is shown as the number inside the circle. The gate 1914 is conducting from its input 1913 on the left to its output 1916 on the right as shown in the diagram. The �sample gate� 1914 is thus conducting between input and output when the control input provides a signal 1.
Each branch also contains a ternary inverter, except the last branch which has no inverter and may be considered having identity inverter i1. The input to the circuit, the scrambled sequence read from the disk, will �see� a certain inverter when both gates in a branch are conducting. Consequently when gates 1907 and 1908 are conducting the signal on input 1911 �sees� inverter 1910 and its inverted value is outputted on 1912.
As a consequence: when [c1 c2 c3] is [0 1 1] the circuit can execute the function �scram� as the signals [0 1 1] will enable the branches with inverters i6, i3 and i2. When [c1 c2 c3] is [2 0 2] the circuit can execute the function �descram_1� as the signals of [2 0 2] will enable the branches with inverters i4, i5 and i1.
The following table shows the user-data in row 1, the scrambling sequence in row 2, the scrambled sequence according to scrambling with function �scram� in row 3 and the result when function �descram_1� is used to descramble in row 5, demonstrating that a matching pair of scrambling/descrambling functions has to be used.
1112001012221221121011220120210012121011
2102000222212100210010102101012001022110
0212221102210101011221101200021211120021
Another way to store the descrambling method on a disk is by storing the inverters that make up the truth table of the required descrambler. The device that realizes the descrambling function is formed by a plurality of memory elements, in the example a plurality of ternary memory elements. Such elements can be formed by binary elements with A/D and D/A converters or by true ternary information retaining devices as described in U.S. Provisional Patent Application No. 60/575,948 titled �Multi-value Coding of Sequences and Multi-value Memory Devices� and in U.S. Provisional Patent Application No. 60/599,781 titled �Multi-valued digital information retaining elements and memory devices.�
Assume that the following table reflects symbolically the truth table of a descrambling function �descram1�. The truth table is created from inverters represented as columns: [a1 a2 a3]; [b1 b2 b3] and [c1 c2 c3]. Which column is active is determined by the current symbol of the descrambling sequence. The current symbol of the scrambled user-data sequence determines the row of the truth table.
descram1
So when for example the current symbol in the descrambling sequence is 0, then the symbol in the scrambled user-data sequence �sees� the inverter [a1 a2 a3].
For illustrative purposes, this is demonstrated in the diagram of a ternary, LFSR based, sequence generator as shown in FIGS. 21 a, 21 b and 21 c. All three sequence generators apply the same single ternary logic function �ter1� of which the truth table is shown in the following table.
All three sequence generators have an identical 4-element shift register. However the generator of FIG. 21 a has as the inputs to the ternary logic device with functions �ter1� the output of element number 3 and 4 of the shift register.
The generator of FIG. 21 b has as the inputs to the ternary logic device with functions �ter1� the output of element number 2 and 4 of the shift register.
The generator of FIG. 21 c has as the inputs to the ternary logic device with functions �ter1� the output of element number 1 and 4 of the shift register.
11120010122212211210112201202100121211110002110102220220020100221021201102020000
11221111002200001122111100220000112211110022000011221111002200001122111100220000
12010010121211002120022011121022122211110210110102020011202112210002012202220000
When the signal provided by control input 2202 is 0 then the gate 2201 will be conducting and the output 2208 of the first element of the shift register will be connected with the input 2207 of the ternary device with function �ter1�.
When the signal provided by control input 2204 is 1 then the gate 2203 will be conducting and the output 2209 of the second element of the shift register will be connected with the input 2207 of the ternary device with function �ter1�.
When the signal provided by control input 2206 is 2 then the gate 2205 will be conducting and the output 2210 of the third element of the shift register will be connected with the input 2207 of the ternary device with function �ter1�.
This aspect of the invention is demonstrated by the diagram of FIG. 23. Circuit 2300 is a ternary sequence generator. It has two individually controlled gates: 2301 and 2303. Gate 2301 is conducting when the control input 2302 provides a signal �0�. In that case the sequence generator will use 3 elements of the shift register. Gate 2303 is conducting when its control input 2304 provides a signal 1. It is assumed that the signal to inputs 2302 and 2304 are provided by the same source. Consequently the conducting state of gates 2301 and 2303 are mutually excluding and when gate 2303 is conducting then gate 2301 is non-conducting and the sequence generator will apply a 4 element shift register.
11201022020001120102202000112010220200011201022020001120102202000112010220200011
It is also possible to generate �high matching correlation�/low non-matching correlation� sequences with LFSR based generators for n=4, n-6 and n=8.
4-valued sequence
303212003302311121130101323001103122232210202131002201233313320
6-valued sequence
22530200145110432520115423444002405231411340422435554430503515025005433535251003
A diagram of the 6-valued LFSR based sequence generator to create this sequence is shown in FIG. 25, with a 3-element shift register. The initial content of the shift register is [1 2 3]. The truth table of the 6-valued logic function �fun6� in the sequence generator is shown in the following table.
Some aspects of the �descrambled sequence� method to determine a digital sum will be further explained with this 6-valued example. The sequence generated by the LFSR based sequence generator only requires an initial content of the shift register and a controlling clock (not shown, but assumed) to be generated. Internally only the 6-valued device with logic function �fun6� can actively change the signal. There is no external signal (except the clock signal, which has a circuit control purpose) that influences the generated signal, and in that sense the generator is different from for instance an LFSR based scrambler.
One can create a descrambling circuit for the generator of FIG. 25. The combination of sequence generator and descrambler is shown in FIG. 26. Circuit 2600 is the sequence generator. It creates a sequence �sig_out� at output 2602. The signal �sig_out� is identical to the output signal �temp1� of 6-valued logic device 2603 with logic function �fun6�. Circuit 2601 is its descrambler. Its input 2604 provides a signal �sig_out�, identical to the output sequence of circuit 2600. The structure of 2601 is a mirror image of 2600: the same shift register and same scrambling function at the same outputs of the shift-register. The only difference with a �common� descrambler is that in this case there is no connection between 2604 and 2605 other than through the descrambling circuit. In this �sequence generator�/descrambler construction the output 2605 will provide a signal �temp2� that is identical to signal �sig_out�.
This result is an aspect of the invented �sequence generator�/descrambler combination and applies to any n-valued logic realization of such a �sequence generator�/descrambler combination.
This result allows for adding a comparing function �comp�. This is shown in FIG. 27. The descrambling circuit 2701 is identical to the descrambling circuit 2601 of FIG. 26 with an additional comparing device 2708 with function �comp� between the input 2704 and output 2705 through a connection 2707 and with input signals provided by input 2707 and input 2709.
The following table shows a truth table of a 6-valued truth table of the device 2708 with 6-valued function �comp� that will generate a 1 on output 2705 when its inputs 2707 and 2709 provide identical signals.
The signals provided by inputs 2707 and 2709, will be identical when the signal provided by 2704 will be identical to the one generated by the output 2702 of circuit 2700. One can change the function �comp� to meet requirements related to a digital sum and expected statistical performance of other sequences inputted on 2704.
8-valued
02423261143637554545151020736635056103372042616431672112765567431472332101774074
46402643467721727025033120256333500615732231012
The sequence is generated by a LFSR based sequence generator which can be described in diagram by FIG. 4. However in this case the shift register is of course an 8-valued shift register and the function �ter1� in FIG. 4 should be replaced by function �fun8� of which the truth table is provided in the following table.
It was suggested in U.S. Pat. No. 6,816,447 titled �Creation of synchronization marks in multilevel optical data storage� by Lee et. al., that two-level synchronization coding can be used on multilevel coded storage disks. While possible and potentially improving the Signal/Noise ratio, the use of fewer than allowed coding levels does not take advantage of better security, synchronization and correlation performance of multilevel data symbols.
In some circumstances it may be required that one uses m-sequences for synchronization or other purposes. It has been demonstrated by the inventor in earlier cited U.S. patent application Ser. No. 10/935,960 titled �Ternary and Multi-value Digital Signal Scramblers, Descramblers and Sequence Generators� that p-valued m-sequences can easily be generated by LFSR-based sequence generators, with p being a prime number.
An optical disk system has a rotating optical disk 2900. The optical signal is read from the disk by way of a pickup unit 2901, which may apply a light source and a detector. The signal read from the disk is processed and demodulated in a processing unit 2902. The signal can be used to control the rotating speed of the spindle 2903 as well as the positioning of the pick-up. The processing unit 2902 requires a sequence on the disk to start synchronizing. Such a sequence, or a method to generate a sequence, is provided by an external source 2904 on a �synchronization and descrambling� data input of the optical disk processing system. Data on an external control input 2905 instructs the system to read a specific segment on the disk, when it is synchronized. The descrambled user-data is outputted on output 2906.
00001022121112210102022220002112112210
�desync�
0020100000111111111xxxxxxxxxxxxxxxxxxxxx
�descram�
xxxxxxxxxxxxxxxxxxx0112222222222210xxxxx
The sequence parts containing �xxxxx . . . � are placeholders, the system does not have to provide an output or may consider that output as irrelevant.
1. a ternary sequence is descrambled according to the descrambling method, (called �desync.m� in this program) intended for the synchronization sequence [0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1]
2. a procedure �track.m� intends to catch the 0s in the descrambled sequence and starts adding 1s when detected to a digital sum.
5. the scrambled data representing user-data is descrambled with a method �descram.m� and generates a sequence of descrambled user-data
This principle is illustrated in FIG. 31. A device 3102 has an input 3101 and an output 3103. The device 3102 changes external signal �sig1� provided by input 3101 by executing a function �sc� into �sig2� provided on output 3103 by the device. A device 3105 has an input 3104 and an output 3106. The device changes a signal �sig2� provided by input 3104 (and on output 3103) by executing a function �ds� into �sig1� provided by the device on output 106. One may say 3102 changes the external signal and 3104 recovers the external signal from the changed signal.
FIG. 32 shows the same devices 3102 and 3104 with the same inputs and same signals, but in a different order. Also the signal �sig2� is now the external signal. One may say that 3104 changes the external signal and 3202 recovers the external signal from the changed signal.
There may be conditions to be fulfilled to exchange the role of scrambler and descrambler. For instance the descrambler of FIG. 30 requires the correct initial content of the shift register to correctly descramble. One cannot apply the �flushing effect� of the shift registers in this case. This property can be applied to increase the security if one is willing to add a synchronization and shift-register initiation circuit for correct operation of the descrambler.
The circuit of FIG. 26 implies that feedback is not always required for a descrambler to work. Building upon that one can create a descrambler of which a diagram is shown in FIG. 33. Assume that this descrambler receives a scrambled (ternary) digital signal �sig_line� on its input 3301. The descrambler has two ternary scrambling devices: 3302 with ternary logic functions �dsr1� and device 3303 with ternary logic function �dsr2�. The descrambler further comprises a ternary shift register with elements 3305, 3306 and 3307. All connections (like in FIG. 26) are forward connected, without feedback. A descrambled ternary signal is outputted on output 3304. To keep things simple it is assumed that ternary scrambling functions �dsr1� and �dsr2� are identical and self-reversing with the following truth table.
The following table shows the ternary input signal to the descrambler �sig_line� and its output �sig_out� when the initial content of the shift register is [0 0 0].
sig_line
01102111100210221021020120111
01211220102101000202101112002
By �reversing� the path of the signal one can create a scrambler as shown in FIG. 34 that will have as input a signal on its input 3401 identical to �sig_out� that will output a signal �sig_line� on its output 3404 that is identical to the signal �sig_line� inputted on 3301 of the descrambler in FIG. 33. The scrambler configuration that would work is shown in FIG. 34 with scrambling devices 3402 and 3403 with the ternary logic functions �scr1� and �scr2�. For the scrambler configuration to work correctly according to the conditions of the descrambler �scr1� and �scr2� have to be identical to the self-reversing ternary scrambling function �dsr1� of which the truth table was provided and the initial content of the shift register with elements 3405, 3406 and 3407 has to be [0 0 0].
6. when the first of a matching pair of scrambler/descrambler circuits has a scrambling function �sp� connected to the output of the pth element of a k-length shifts register (p being determined as counting from the circuit input up to the output) then the matching circuit has a scrambling function �dp� connected to the output of shift register (k−p+1) being determined as counting from the circuit input up to the output.
7. an n-valued scrambling function �sp� can be a reversible n-valued function. Its corresponding scrambling function �dp� in the matching circuit should be the n-valued reversible function that reverses �sp�.
Multi-level coding and decoding devices are disclosed in United States Patent Application 2003/0063677 entitled: �Multi-level coding for digital communication� by Jason A. Mix et. al., which is hereby incorporated by reference.
The diagram of FIG. 38 a shows one realization of the circuits 109, 114 and 110 of FIG. 1 a. The caption of circuit 110 in FIG. 1 a says �data separation�. While non-user data may actually be stopped from being outputted on 111, it may also be that a separate signal (like a signal outputted on 3804 in FIG. 38 a) indicates that data may be ignored, because it is not recognized as user-data. The configuration as shown in FIG. 38 a is the reading counterpart of the writing circuit as shown in FIG. 37 a. In this configuration both synchronization data and end-user data are scrambled and need to be descrambled.
The configuration as shown in FIG. 38 b is the reading counterpart of the writing circuit as shown in FIG. 37 b. In this configuration both synchronization data and end-user data are scrambled and need to be descrambled. This is done by descrambler 3806. The descrambled signal is outputted on 3802 leading to synchronization unit 3803 (which in this configuration does not include a descrambler) and to end-user data output 3805. When the synchronization sequence is detected by 3803 a �detection achieved� signal is outputted on 3804, informing additional circuitry (not shown) that data outputted on 3805 should be considered to be valid end-user data.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3988538 *Feb 26, 1975Oct 26, 1976International Standard Electric CorporationDigital data scrambler and descramblerUS5007037Jul 29, 1988Apr 9, 1991Quantex CorporationOptical disk drive system utilizing electron trapping media for data storageUS5136573Jun 28, 1989Aug 4, 1992Kabushiki Kaisha ToshibaInformation recording apparatus and methodUS5144615Dec 22, 1989Sep 1, 1992Kabushiki Kaisha ToshibaApparatus and method for recording and reproducing multi-level informationUS5195082Apr 22, 1992Mar 16, 1993Optex CorporationOptical disk structures for electron trapping optical memory mediaUS5537382Nov 22, 1994Jul 16, 1996Optex CorporationPartial response coding for a multi-level optical recording channelUS5745522Nov 9, 1995Apr 28, 1998General Instrument Corporation Of DelawareRandomizer for byte-wise scrambling of dataUS5748117May 12, 1995May 5, 1998Optex CorporationM=8 (1,3) runlength limited code for multi-level dataUS5850382 *Apr 9, 1997Dec 15, 1998Matsushita Electrical Industrial Co., Ltd.Optical disk having a rewritable area and a read-only areaUS6148428May 21, 1998Nov 14, 2000Calimetrics, Inc.Method and apparatus for modulation encoding data for storage on a multi-level optical recording mediumUS6201870Mar 6, 1998Mar 13, 2001Massachusetts Institue Of TechnologyPseudorandom noise sequence generatorUS6275458Feb 18, 1999Aug 14, 2001Terrence L. WongMethod and apparatus for reading and writing a multi-level signal from an optical discUS6389080Mar 6, 1999May 14, 2002Lockheed Martin Corp.Random phase shift keyingUS6430246Oct 10, 2000Aug 6, 2002Interdigital Technology CorporationMethod and apparatus for generating a stream cipherUS6459722Dec 4, 2000Oct 1, 2002Texas Instruments IncorporatedPseudorandom noise generator for WCDMAUS6463448Sep 30, 1999Oct 8, 2002Agere Systems Guardian Corp.Linear intrasummed multiple-bit feedback shift registerUS6563881 *Jul 9, 1999May 13, 2003Sony CorporationCommunication method and transmitter with transmission symbols arranged at intervals on a frequency axisUS6574283Aug 11, 1998Jun 3, 2003Sony CorporationCommunication method, transmission and reception apparatuses, and cellular radio communication systemUS6590860Mar 17, 1998Jul 8, 2003Sony CorporationReceiving device and signal receiving methodUS6608807Feb 2, 2000Aug 19, 2003Calimetrics, Inc.Generating a multilevel calibration sequence for precompensationUS6657933Jul 19, 2001Dec 2, 2003Calimetrics, Inc.Method and apparatus for reading and writing a multilevel signal from an optical discUS6763363Dec 2, 1999Jul 13, 2004Honeywell International Inc.Computer efficient linear feedback shift registerUS6816408Apr 15, 2003Nov 9, 2004Micron Technology, Inc.Memory device with multi-level storage cellsUS6816447May 31, 2001Nov 9, 2004Lsi Logic CorporationCreation of synchronization marks in multilevel optical data storageUS6816555Feb 15, 2001Nov 9, 2004Sony CorporationSignal component demultiplexing apparatus, filter apparatus, receiving apparatus, communication apparatus, and communication methodUS6907062Aug 6, 2001Jun 14, 2005Broadcom CorporationPRBS generator selection in modem communicationUS6909704Mar 2, 2001Jun 21, 2005Sony CorporationCommunication system that rejects connections based on total transmission energyUS6961369Nov 9, 2000Nov 1, 2005Aware, Inc.System and method for scrambling the phase of the carriers in a multicarrier communications systemUS6983413 *Mar 22, 2001Jan 3, 2006Kabushiki Kaisha ToshibaData processing method using error-correcting code and an apparatus using the same methodUS7061888Mar 2, 2001Jun 13, 2006Sony CorporationCommunication method and apparatus in which a total power of power control information is a fixed valuedUS7099469 *Oct 17, 2001Aug 29, 2006Motorola, Inc.Method of scrambling and descrambling data in a communication systemUS7133458Aug 25, 2004Nov 7, 2006Sony CorporationSignal component demultiplexing apparatus, filter apparatus, receiving apparatus, communication apparatus, and communication methodUS7177424May 17, 2000Feb 13, 2007Hitachi, Ltd.Cryptographic apparatus and methodUS7236433Jun 19, 2003Jun 26, 2007Hitachi, Ltd.System and method of recording and reproducing informationUS7346165 *May 28, 2002Mar 18, 2008Lg Electronics Inc.Apparatus and method for generating scrambling code in mobile communication systemUS20020054682Aug 8, 2001May 9, 2002Stmicroelectronics S.R.L.Method and device for protecting the contents of an electronic documentUS20030063677Sep 28, 2001Apr 3, 2003Intel CorporationMulti-level coding for digital communicationUS20030072445 *Oct 17, 2001Apr 17, 2003Kuhlman Douglas A.Method of scrambling and descrambling data in a communication systemUS20040156284Feb 2, 2004Aug 12, 2004Wong Terrence L.Method and apparatus for reading and writing a multilevel signal from an optical disc oscillators* Cited by examinerNon-Patent CitationsReference1Data Interchange on Read-Only 120 MM Optical Data Disks (CD-ROM); Standard ECMA-130, 2nd Edition-Jun. 1996, 57 pages.2Data Interchange on Read-Only 120 MM Optical Data Disks (CD-ROM); Standard ECMA-130, 2nd Edition�Jun. 1996, 57 pages.3Hirofumi Haeiwa et al., �Precise formation of fine pits on birefringent film for multi-level optical data storage.�, Jpn. J. Appl. Phys, 2002, vol. 41 (1), n�7B, pp. 4841-4844.4Hirofumi Haeiwa et al., 'Precise formation of fine pits on birefringent film for multi-level optical data storage.', Jpn. J. Appl. Phys, 2002, vol. 41 (1), n�7B, pp. 4841-4844.5Mathworks, "Communications Blockset Descrambler", http://www.mathworks.de/access/helpdeskr13/help/toolbox/commblks/ref/descrambler.html, website, 1994-2007.6Mathworks, "Communications Blockset Scrambler", http://www.mathworks.de/access/helpdeskr14/help/toolbox/commblks/ref/scrambler.html, (before 2003),1-2.7Mathworks, "Descrambler Blocks (Communications Blockset)", Matlab 7.1.0 R14 Help Screen, (2005).8Steven McLaughlin, et al., �Advanced Coding and Signal Processing for Multilevel Write-Once and ReWritable Optical Storage.�, ODS 2001, Santa Fe, NM, 3 pages.9Steven McLaughlin, et al., 'Advanced Coding and Signal Processing for Multilevel Write-Once and ReWritable Optical Storage.', ODS 2001, Santa Fe, NM, 3 pages.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8725943Jan 16, 2013May 13, 2014International Business Machines CorporationMethod and system for secure data storageUS8732560 *May 8, 2012May 20, 2014Infineon Technologies AgMethod and device for correction of ternary stored binary dataUS8817928 *May 31, 2011Aug 26, 2014Ternarylogic LlcMethod and apparatus for rapid synchronization of shift register related symbol sequencesUS8860594May 17, 2012Oct 14, 2014Brilliant Points, Inc.System and method for digital signalingUS20110293062 *May 31, 2011Dec 1, 2011Ternarylogic LlcMethod and Apparatus for Rapid Synchronization of Shift Register Related Symbol SequencesUS20130305119 *May 8, 2012Nov 14, 2013Infineon Technologies AgMethod and Device for Correction of Ternary Stored Binary Data* Cited by examinerClassifications U.S. Classification714/701, 714/778, 380/275, 326/59International ClassificationG06F11/00Cooperative ClassificationG11B2220/2537, G11B20/0021, G11B20/00086European ClassificationG11B20/00P5, G11B20/00PLegal EventsDateCodeEventDescriptionOct 13, 2013FPAYFee paymentYear of fee payment: 4Mar 14, 2005ASAssignmentOwner name: TERNARYLOGIC LLC, NEW JERSEYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:LABLANS, PETER;REEL/FRAME:016352/0635Effective date: 20050225Owner name: TERNARYLOGIC LLC,NEW JERSEYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:LABLANS, PETER;US-ASSIGNMENT DATABASE UPDATED:20100525;REEL/FRAME:16352/635RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services