Bit-reversal permutation (original) (raw)

About DBpedia

Em matemática aplicada, uma ordenação bit-reversa ou uma permutação bit-reversa é uma permutação de uma seqüência de n itens, onde n = 2k é uma potência de dois. Ele é definido pela indexação de elementos da sequência, os números de 0 a n − 1 e, em seguida, invertendo as representações binárias de cada um desses números (acolchoado para que cada um destes números binários tenha comprimento de exatamente k). Cada item é mapeado para a nova posição dada por este valor invertido. O bit de reversão de permutação é uma involução, então repetindo a mesma permutação duas vezes retorna-se para a ordenação original sobre os itens.

thumbnail

Property Value
dbo:abstract In applied mathematics, a bit-reversal permutation is a permutation of a sequence of items, where is a power of two. It is defined by indexing the elements of the sequence by the numbers from to , representing each of these numbers by its binary representation (padded to have length exactly ), and mapping each item to the item whose representation has the same bits in the reversed order. Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an involution. This permutation can be applied to any sequence in linear time while performing only simple index calculations. It has applications in the generation of low-discrepancy sequences and in the evaluation of fast Fourier transforms. (en) Em matemática aplicada, uma ordenação bit-reversa ou uma permutação bit-reversa é uma permutação de uma seqüência de n itens, onde n = 2k é uma potência de dois. Ele é definido pela indexação de elementos da sequência, os números de 0 a n − 1 e, em seguida, invertendo as representações binárias de cada um desses números (acolchoado para que cada um destes números binários tenha comprimento de exatamente k). Cada item é mapeado para a nova posição dada por este valor invertido. O bit de reversão de permutação é uma involução, então repetindo a mesma permutação duas vezes retorna-se para a ordenação original sobre os itens. (pt)
dbo:thumbnail wiki-commons:Special:FilePath/Hammersley_set_2D.svg?width=300
dbo:wikiPageID 25692725 (xsd:integer)
dbo:wikiPageLength 11992 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1120557118 (xsd:integer)
dbo:wikiPageWikiLink dbr:Power_of_two dbr:Binary_search_tree dbr:Permutation dbc:Permutations dbr:Low-discrepancy_sequence dbr:Cooley–Tukey_FFT_algorithm dbr:Linear_time dbr:Lower_bound dbr:Van_der_Corput_sequence dbc:Combinatorial_algorithms dbr:Data_structures dbr:Fast_Fourier_transform dbr:Radix dbr:Involution_(mathematics) dbr:Kaczmarz_method dbc:FFT_algorithms dbr:Mixed_radix dbr:In-place_algorithm dbr:Random-access_machine dbr:Sequence dbr:Memory_hierarchy dbr:Unit_interval dbr:Fixed-point_arithmetic dbr:Vectored_I/O dbr:Dyadic_rational_number dbr:In-place dbr:Binary_representation dbr:Splay_trees dbr:File:Hammersley_set_2D.svg
dbp:wikiPageUsesTemplate dbt:Not_a_typo dbt:Short_description
dct:subject dbc:Permutations dbc:Combinatorial_algorithms dbc:FFT_algorithms
gold:hypernym dbr:Permutation
rdf:type yago:WikicatCombinatorialAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Change107296428 yago:Event100029378 yago:Happening107283608 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Substitution107443761 yago:Variation107337390 yago:WikicatFFTAlgorithms yago:WikicatPermutations
rdfs:comment Em matemática aplicada, uma ordenação bit-reversa ou uma permutação bit-reversa é uma permutação de uma seqüência de n itens, onde n = 2k é uma potência de dois. Ele é definido pela indexação de elementos da sequência, os números de 0 a n − 1 e, em seguida, invertendo as representações binárias de cada um desses números (acolchoado para que cada um destes números binários tenha comprimento de exatamente k). Cada item é mapeado para a nova posição dada por este valor invertido. O bit de reversão de permutação é uma involução, então repetindo a mesma permutação duas vezes retorna-se para a ordenação original sobre os itens. (pt) In applied mathematics, a bit-reversal permutation is a permutation of a sequence of items, where is a power of two. It is defined by indexing the elements of the sequence by the numbers from to , representing each of these numbers by its binary representation (padded to have length exactly ), and mapping each item to the item whose representation has the same bits in the reversed order. Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an involution. (en)
rdfs:label Bit-reversal permutation (en) Ordenação bit-reversa (pt)
owl:sameAs freebase:Bit-reversal permutation yago-res:Bit-reversal permutation wikidata:Bit-reversal permutation dbpedia-fa:Bit-reversal permutation dbpedia-pt:Bit-reversal permutation https://global.dbpedia.org/id/4ZCjB
prov:wasDerivedFrom wikipedia-en:Bit-reversal_permutation?oldid=1120557118&ns=0
foaf:depiction wiki-commons:Special:FilePath/Hammersley_set_2D.svg
foaf:isPrimaryTopicOf wikipedia-en:Bit-reversal_permutation
is dbo:wikiPageRedirects of dbr:Bit-reversal dbr:Bit-reversed_order dbr:Bit_reversal dbr:Digit-reversal_permutation
is dbo:wikiPageWikiLink of dbr:Calkin–Wilf_tree dbr:List_of_numerical_analysis_topics dbr:List_of_permutation_topics dbr:Organizationally_unique_identifier dbr:Cooley–Tukey_FFT_algorithm dbr:Van_der_Corput_sequence dbr:Walsh_matrix dbr:Stern–Brocot_tree dbr:Bit-reversal dbr:Bit-reversed_order dbr:Bit_reversal dbr:Digit-reversal_permutation
is foaf:primaryTopic of wikipedia-en:Bit-reversal_permutation