公开(公告)号：US07133853B2

公开(公告)日：2006-11-07

申请号：US10626057

申请日：2003-07-24

申请人： Tom Richardson ,  Vladimir Novichkov

发明人： Tom Richardson ,  Vladimir Novichkov

IPC分类号： G06N5/00

CPC分类号： H03M13/6356 ,  G06N3/02 ,  H03M13/1114 ,  H03M13/1131 ,  H03M13/1137 ,  H03M13/1148 ,  H03M13/116 ,  H03M13/1168 ,  H03M13/1177 ,  H03M13/6362 ,  H03M13/6505 ,  H03M13/6566

摘要： Methods and apparatus for decoding codewords using message passing decoding techniques which are particularly well suited for use with low density parity check (LDPC) codes and long codewords are described. The described methods allow decoding graph structures which are largely comprised of multiple identical copies of a much smaller graph. Copies of the smaller graph are subject to a controlled permutation operation to create the larger graph structure. The same controlled permutations are directly implemented to support message passing between the replicated copies of the small graph. Messages corresponding to individual copies of the graph are stored in a memory and accessed in sets, one from each copy of the graph, using a SIMD read or write instruction. The graph permutation operation may be implemented by simply reordering messages, e.g., using a cyclic permutation operation, in each set of messages read out of a message memory so that the messages are passed to processing circuits corresponding to different copies of the small graph.

公开(公告)号：US20060242093A1

公开(公告)日：2006-10-26

申请号：US11455014

申请日：2006-06-16

申请人： Tom Richardson ,  Vladimir Novichkov

发明人： Tom Richardson ,  Vladimir Novichkov

IPC分类号： G06N3/02

CPC分类号： H03M13/6356 ,  G06N3/02 ,  H03M13/1114 ,  H03M13/1131 ,  H03M13/1137 ,  H03M13/1148 ,  H03M13/116 ,  H03M13/1168 ,  H03M13/1177 ,  H03M13/6362 ,  H03M13/6505 ,  H03M13/6566

摘要： Methods and apparatus for decoding codewords using message passing decoding techniques which are particularly well suited for use with low density parity check (LDPC) codes and long codewords are described. The described methods allow decoding graph structures which are largely comprised of multiple identical copies of a much smaller graph. Copies of the smaller graph are subject to a controlled permutation operation to create the larger graph structure. The same controlled permutations are directly implemented to support message passing between the replicated copies of the small graph. Messages corresponding to individual copies of the graph are stored in a memory and accessed in sets, one from each copy of the graph, using a SIMD read or write instruction. The graph permutation operation may be implemented by simply reordering messages, e.g., using a cyclic permutation operation, in each set of messages read out of a message memory so that the messages are passed to processing circuits corresponding to different copies of the small graph.

公开(公告)号：US20060117240A1

公开(公告)日：2006-06-01

申请号：US10985475

申请日：2004-11-10

申请人： Vladimir Novichkov ,  Tom Richardson ,  Vince Loncke

发明人： Vladimir Novichkov ,  Tom Richardson ,  Vince Loncke

IPC分类号： H03M13/00

CPC分类号： H03M13/116 ,  H03M13/1137

摘要： High throughput parallel LDPC decoders are designed and implemented using hierarchical design and layout optimization. In a first level of hierarchy, the node processors are grouped on the LDPC decoder chip, physically co-locating the processing elements in a small area. In a second level of hierarchy, clusters, e.g., subsets, of the processing elements are grouped together and a pipeline stage including pipeline registers is introduced on the boundaries between clusters. Register to register path propagating signals are keep localized as much as possible. The switching fabric coupling the node processors with edge message memory is partitioned into separate switches. Each separate switch is split into combinational switching layers. Design hierarchies are created for each layer, localizing the area where the interconnect is dense and resulting in short interconnect paths thus limiting signal delays in routing.

公开(公告)号：US06957375B2

公开(公告)日：2005-10-18

申请号：US10788115

申请日：2004-02-26

申请人： Tom Richardson

发明人： Tom Richardson

IPC分类号： G06F9/46 ,  H03M7/00 ,  H03M13/11 ,  H03M13/13 ,  H03M13/27

CPC分类号： H03M13/6508 ,  H03M13/1137 ,  H03M13/116 ,  H03M13/1168 ,  H03M13/118 ,  H03M13/6356 ,  H03M13/6362 ,  H03M13/6505 ,  H03M13/6516

摘要： Methods and apparatus of the present invention can be used to implement a communications system wherein different devices using the same LDPC code can be implemented using different levels of parallelism. The use of a novel class of LDPC codes makes such differences in parallelism possible. Use of a factorable permuter in various embodiments of the invention make LDPC devices with different levels of parallelism in the encoder and decoder relatively easy to implement when using the codes in the class of LDPC codes discussed herein. The factorable permuter may be implemented as a controllable multi-stage switching devices which performs none, one, or multiple sequential reordering operations on a Z element vector passed between memory and a Z element vector processor, with the switching one individual vectors being controlled in accordance with the graph structure of the code being implemented.

摘要翻译： 本发明的方法和装置可用于实现通信系统，其中可以使用不同级别的并行性来实现使用相同LDPC码的不同设备。 使用新颖的LDPC码类使得并行性的这种差异成为可能。 在本发明的各种实施例中使用因子式置换器在编码器和解码器中使用具有不同级别的并行性的LDPC装置在使用本文所讨论的LDPC码类中的代码时相对容易实现。 可因素置换器可以被实现为对在存储器和Z元素向量处理器之间传递的Z元素向量执行无，一个或多个顺序重排序操作的可控多级切换装置，其中切换一个单独的向量根据 其代码的图形结构正在被实现。

公开(公告)号：US09880283B2

公开(公告)日：2018-01-30

申请号：US12169742

申请日：2008-07-09

申请人： Tom Richardson ,  Santiago Romero ,  David S. Wisherd ,  Michael A. Wohl

发明人： Tom Richardson ,  Santiago Romero ,  David S. Wisherd ,  Michael A. Wohl

IPC分类号： G08B5/22 ,  G01S19/09 ,  G01S19/07 ,  G01S19/14 ,  G01S19/48

CPC分类号： G01S19/09 ,  G01S19/07 ,  G01S19/14 ,  G01S19/48

摘要： A system is provided for tracking an asset within a geographic area. The system includes an antenna mast supportable by, and extending upward from, an object configured to move or facilitate movement of the asset. The antenna mast is capable of supporting a plurality of wireless locating units of a plurality of geo-spatial positioning systems, which are configured to locate a respective one or more locating units, and thereby the asset, within the geographic area. The system also includes a controller positionable on the object and configured to control operation of the wireless locating units. The controller is further configured to direct transmission of data to a host via one of the locating units or another wireless transmitter, and in a manner that accounts for a wireless link between the respective locating unit or other wireless transmitter and the host.

公开(公告)号：US20100153812A1

公开(公告)日：2010-06-17

申请号：US12620123

申请日：2009-11-17

申请人： Hui Jin ,  Tom Richardson ,  Vladimir Novichkov

发明人： Hui Jin ,  Tom Richardson ,  Vladimir Novichkov

IPC分类号： H03M13/05 ,  G06F11/10

CPC分类号： H03M13/6362 ,  H03M13/1102 ,  H03M13/1137 ,  H03M13/116 ,  H03M13/1182

摘要： Methods and apparatus for encoding codewords which are particularly well suited for use with low density parity check (LDPC) codes and long codewords are described. The described methods allow encoding graph structures which are largely comprised of multiple identical copies of a much smaller graph. Copies of the smaller graph are subject to a controlled permutation operation to create the larger graph structure. The same controlled permutations are directly implemented to support bit passing between the replicated copies of the small graph. Bits corresponding to individual copies of the graph are stored in a memory and accessed in sets, one from each copy of the graph, using a SIMD read or write instruction. The graph permutation operation may be implemented by simply reordering bits, e.g., using a cyclic permutation operation, in each set of bits read out of a bit memory so that the bits are passed to processing circuits corresponding to different copies of the small graph.

摘要翻译： 描述了特别适用于低密度奇偶校验（LDPC）码和长码字的码字的编码方法和装置。 所描述的方法允许编码图形结构，其大部分由更小的图的多个相同副本组成。 较小图的副本经受受控置换操作以创建较大的图形结构。 直接实现相同的受控置换，以支持小图的复制副本之间的位传递。 与图形的各个副本对应的位存储在存储器中，并使用SIMD读取或写入指令以组合的形式从图形的每个副本中进行访问。 图形置换操作可以通过在比特存储器中读出的每组比特中简单地重新排序比特，例如使用循环置换操作来实现，使得比特被传递到对应于小图的不同副本的处理电路。

公开(公告)号：US07673223B2

公开(公告)日：2010-03-02

申请号：US11178951

申请日：2005-07-11

申请人： Tom Richardson ,  Vladimir Novichkov

发明人： Tom Richardson ,  Vladimir Novichkov

IPC分类号： H03M13/00

CPC分类号： G06N3/02 ,  H03M13/1102 ,  H03M13/1111 ,  H03M13/1117 ,  H03M13/112 ,  H03M13/1125 ,  H03M13/1131 ,  H03M13/1134 ,  H03M13/1137 ,  H03M13/114 ,  H03M13/1145 ,  H03M13/6362 ,  H03M13/6502 ,  H03M13/6577 ,  H03M13/658

摘要： Techniques for implementing message passing decoders, e.g., LDPC decoders, are described. To facilitate hardware implementation messages are quantized to integer multiples of ½ ln2. Messages are transformed between more compact variable and less compact constraint node message representation formats. The variable node message format allows variable node message operations to be performed through simple additions and subtractions while the constraint node representation allows constraint node message processing to be performed through simple additions and subtractions. Variable and constraint nodes are implemented using an accumulator module, subtractor module and delay pipeline. The accumulator module generates an accumulated message sum. The accumulated message sum for a node is stored and then delayed input messages from the delay pipeline are subtracted there from to generate output messages. The delay pipeline includes a variable delay element making it possible to sequentially perform processing operations corresponding to nodes of different degrees.

摘要翻译： 描述了用于实现消息传递解码器（例如，LDPC解码器）的技术。 为了便于硬件实现，消息被量化为1/2 ln2的整数倍。 消息在更紧凑的可变和不紧凑的约束节点消息表示格式之间转换。 变量节点消息格式允许通过简单的加法和减法执行变量节点消息操作，而约束节点表示允许通过简单的加法和减法执行约束节点消息处理。 变量和约束节点使用累加器模块，减法器模块和延迟管道来实现。 累加器模块产生一个累加的消息和。 存储节点的累积消息总和，然后从延迟流水线中减去延迟的输入消息，从而生成输出消息。 延迟流水线包括可变延迟元件，使得可以顺序地执行与不同程度的节点相对应的处理操作。

公开(公告)号：US07627801B2

公开(公告)日：2009-12-01

申请号：US11174790

申请日：2005-07-05

申请人： Hui Jin ,  Tom Richardson ,  Vladimir Novichkov

发明人： Hui Jin ,  Tom Richardson ,  Vladimir Novichkov

IPC分类号： H03M13/00 ,  H03M13/05

CPC分类号： H03M13/6362 ,  H03M13/1102 ,  H03M13/1137 ,  H03M13/116 ,  H03M13/1182

摘要： Methods and apparatus for encoding codewords which are particularly well suited for use with low density parity check (LDPC) codes and long codewords are described. The described methods allow encoding graph structures which are largely comprised of multiple identical copies of a much smaller graph. Copies of the smaller graph are subject to a controlled permutation operation to create the larger graph structure. The same controlled permutations are directly implemented to support bit passing between the replicated copies of the small graph. Bits corresponding to individual copies of the graph are stored in a memory and accessed in sets, one from each copy of the graph, using a SIMD read or write instruction. The graph permutation operation may be implemented by simply reordering bits, e.g., using a cyclic permutation operation, in each set of bits read out of a bit memory so that the bits are passed to processing circuits corresponding to different copies of the small graph.

摘要翻译： 描述了特别适用于低密度奇偶校验（LDPC）码和长码字的码字的编码方法和装置。 所描述的方法允许编码图形结构，其大部分由更小的图的多个相同副本组成。 较小图的副本经受受控置换操作以创建较大的图形结构。 直接实现相同的受控置换，以支持小图的复制副本之间的位传递。 与图形的各个副本对应的位存储在存储器中，并使用SIMD读取或写入指令以组合的形式从图形的每个副本中进行访问。 图形置换操作可以通过在比特存储器中读出的每组比特中简单地重新排序比特，例如使用循环置换操作来实现，使得比特被传递到对应于小图的不同副本的处理电路。

公开(公告)号：US20090177869A1

公开(公告)日：2009-07-09

申请号：US12348674

申请日：2009-01-05

申请人： Vladimir Novichkov ,  Tom Richardson

发明人： Vladimir Novichkov ,  Tom Richardson

IPC分类号： G06F9/302 ,  H03M13/05 ,  G06F11/10

CPC分类号： H03M7/24 ,  H03M13/1117 ,  H03M13/112 ,  H03M13/1125 ,  H03M13/6577 ,  H03M13/658

摘要： In modern iterative coding systems such as LDPC decoder and turbo-convolutional decoder in which the invention may be used, the core computations can often be reduced to a sequence of additions and subtractions alternating between logarithm and linear domains A computationally efficient and robust approximation method for log and exp functions is described which involves using a simple bit mapping between fixed point fractional data format and floating point format. The method avoids costly lookup tables and complex computations and further reduces the core processing to a sequence of additions and subtractions using alternating fixed point and floating point processing units. The method is well suited for use in highly optimized hardware implementations which can take advantage of modern advances in standard floating point arithmetic circuit design as well as for software implementation on a wide class of processors equipped with FPU where the invention avoids the need for a typical multi-cycle series of log/exp instructions and especially on a SIMD FPU-equipped processors where log/exp functions are typically scalar.

摘要翻译： 在诸如可以使用本发明的LDPC解码器和turbo卷积解码器的现代迭代编码系统中，核心计算通常可以减少到在对数和线性域之间交替的加法和减法序列。计算有效和鲁棒的近似方法 描述了log和exp函数，其涉及使用固定点分数据格式和浮点格式之间的简单位映射。 该方法避免了昂贵的查找表和复杂的计算，并且使用交替的固定点和浮点处理单元进一步将核心处理减少到一系列的加法和减法。 该方法非常适合用于高度优化的硬件实现，可以利用标准浮点运算电路设计的现代进步以及配备FPU的广泛类型处理器上的软件实现，其中本发明避免了对典型 多周期系列的log / exp指令，特别是在一个SIMD FPU处理器上，其中log / exp函数通常是标量的。

公开(公告)号：US07552097B2

公开(公告)日：2009-06-23

申请号：US11455014

申请日：2006-06-16

申请人： Tom Richardson ,  Vladimir Novichkov

发明人： Tom Richardson ,  Vladimir Novichkov

IPC分类号： G06N5/00

CPC分类号： H03M13/6356 ,  G06N3/02 ,  H03M13/1114 ,  H03M13/1131 ,  H03M13/1137 ,  H03M13/1148 ,  H03M13/116 ,  H03M13/1168 ,  H03M13/1177 ,  H03M13/6362 ,  H03M13/6505 ,  H03M13/6566

摘要： Methods and apparatus for decoding codewords using message passing decoding techniques which are particularly well suited for use with low density parity check (LDPC) codes and long codewords are described. The described methods allow decoding graph structures which are largely comprised of multiple identical copies of a much smaller graph. Copies of the smaller graph are subject to a controlled permutation operation to create the larger graph structure. The same controlled permutations are directly implemented to support message passing between the replicated copies of the small graph. Messages corresponding to individual copies of the graph are stored in a memory and accessed in sets, one from each copy of the graph, using a SIMD read or write instruction. The graph permutation operation may be implemented by simply reordering messages, e.g., using a cyclic permutation operation, in each set of messages read out of a message memory so that the messages are passed to processing circuits corresponding to different copies of the small graph.

摘要翻译： 描述了使用特别适用于低密度奇偶校验（LDPC）码和长码字的消息传递解码技术来解码码字的方法和装置。 所描述的方法允许解码图形结构，其主要由较小图的多个相同副本组成。 较小图的副本经受受控置换操作以创建较大的图形结构。 直接实现相同的受控置换，以支持小图的复制副本之间的消息传递。 与图形的各个副本相对应的消息存储在存储器中，并使用SIMD读或写指令从集合的每个副本中进行访问。 可以通过在从消息存储器读出的每组消息中简单地重新排序消息（例如使用循环置换操作）来实现图表置换操作，使得消息被传递到对应于小图的不同副本的处理电路。